砝码称重问题【dp】

设有 1g ， 2g ， 3g ， 5g ， 10g ， 20g 的砝码各若干枚 ( 其 总重≤

1000g) ，要 求：

输入：

       a1   a2   a3   a4   a5   a6( 表示 1g 砝码有 a1 个， 2g 砝码有 a2

个， ......20g 砝码有 a6 个 )

输出：

       Total=N (N 表示用这些砝码能称出的不同重量的个数，但不包括

一个砝码也不用的情况 )

   输入样例： 1  1  0   0   0   0

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

量。

code:

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int dp[10005],n,s[7],num,sum=0,i,j,z,ans[1005];
	int m[]={1,2,3,5,10,20};
	cout<<"请输入1g,2g,3g,5g,10g,20g，每种砝码的个数"<<endl;
	for(i=0;i<6;i++)
	{
		cin>>s[i];
		sum+=s[i]*m[i];
	}
	memset(dp,0,sizeof(dp));
	dp[0]=1;
	dp[sum]=1;
	for(i=0;i<6;i++)
		for(j=0;j<s[i];j++)
			for(z=sum;z>=m[i];z--)
				if(dp[z-m[i]]==1)
					dp[z]=1;
	for(i=1,j=0;i<=sum;i++)
		if(dp[i]==1)
		{
			num++;
			ans[j++]=i;
		}
	cout<<"Total="<<num<<",表示可以称出 ";
	for(i=0;i<j-1;i++){
		cout<<ans[i]<<"g,";
	}
	cout<<ans[j-1]<<"g "<<j<<"种不同的重量。"<<endl; 
	return 0;
}