天平问题：砝码10 20 50 100 500若干， 第一行输入5种砝码的个数（0≤每种砝码的个数≤10），输出可以称多少种重量的物品，0不算

多重背包问题

/*天平问题：砝码10  20  50  100  500若干，
 第一行输入5种砝码的个数（0≤每种砝码的个数≤10），输出可以称多少种重量的物品，0不算*/


#include<cstdio>
#define maxn 1000
using namespace std;
int s[5],v[5]={10,20,50,100,500};
bool f[maxn+100];
int main()
{
    int i,j,k,sum=0;
    for(i=0;i<5;i++)
        scanf("%d",&s[i]),sum+=(v[i]*s[i]);
    
    for(f[0]=1,i=0;i<5;i++)
        for(j=1;j<=s[i];j++)
            for(k=sum;k>=v[i];k--)
                if(f[k-v[i]])f[k]=1;
    
    for(k=0,i=1;i<=sum;i++)if(f[i])k++;
    printf("Total=%d\n",k);
    return 0;
}