设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=100,000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
1 1 0 0 0 0
Total=3
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[10]; 4 int h[10]; 5 bool f[200000]; 6 int ans; 7 int sum; 8 int main(){ 9 a[1]=1; a[2]=2; a[3]=3; a[4]=5; a[5]=10; a[6]=20; 10 for(int i=1;i<=6;i++) scanf("%d",&h[i]),sum+=a[i]*h[i]; 11 f[0]=true; 12 for(int i=1;i<=6;i++){ 13 for(int v=sum;v>0;v--){ 14 for(int k=0;k<=h[i];k++){ 15 if(k*a[i]<=v&&f[v-k*a[i]]==true){ 16 f[v]=true; 17 } 18 } 19 } 20 } 21 for(int i=1;i<=sum;i++){ 22 if(f[i]==true) ans++; 23 } 24 cout<<"Total="<<ans; 25 return 0; 26 }
原文：http://www.cnblogs.com/CXCXCXC/p/4906806.html