[提交][状态][讨论版]

题目描述

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000）。

现在给你这六种砝码的数量，请你计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。

如输入：1 1 0 0 0 0

输出：Total=3 表示可以称出1g，2g，3g三种不同的重量。

输入

仅1行： 六个整数a1,a2,a3,a4,a5,a6，分别表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个。

输出

第1行：输出所有可以称出的不同重量值，从小到大排列，每个数之间用一个空格隔开。

第2行：输出Total=N。（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

样例输入 1 1 0 0 0 0

样例输出 1 2 3 Total=3

#include <bits/stdc++.h>
using namespace std;
const int w[]={1,2,3,5,10,20};
const int N=sizeof(w)/sizeof(int);
int a[N];
int s[1010];
int main()
{
    int sum=0;
    for(int i=0;i<N;i++) 
	{
        cin>>a[i];
        sum+=a[i]*w[i];
    }
    s[0]=1;
    for(int i=0;i<N;i++)
        for(int j=1;j<=a[i];j++)
            for(int k=sum;k>=w[i];k--)
                if(s[k-w[i]]==1) s[k]=1;
    int ans=0;
    for(int i=1;i<=sum;i++)
        if(s[i]==1) 
		{
			ans++;
			cout<<i<<" ";
		}
    cout<<endl<<"Total="<<ans<<endl;
    return 0;
}