题目描述

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

输入格式

依次从轻到重输入各个砝码的个数

输出格式

输出方式：Total=N

（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

输入样例

1 1 0 0 0 0

输出样例

Total=3

解法

思路

本题有两种解题思路

  1. 采用多重背包模板，给定了t为1000的背包和N种体积为w[i]价值为v[i]的物品，各个物品有数量限制。本题只不过价值和体积是相等的，f[j]就用这些砝码能称出的小于j的最大重量，而j是从1开始增长，所以f[j]中存储了所有的情况，只需要对f[j]去重，剩下的重量种数就是Total

  2. 采用0/1背包模板，将n[i]个i复制出n[i]个，这n[i]个不再当成同一种，而是n[i]种体积和价值相同的物品。但是对于本题已经给出了各个砝码的费用和价值，就不太适合用这种方法了。

易错点

如果采用二维数组，f[i-1][j]到f[i][j]的复制条件容易丢

二维数组实现

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main(){
    int t=1000,N=6;
    int f[7][1001]={},w[7]={0,1,2,3,5,10,20},v[7]={0,1,2,3,5,10,20},n[7]={};
    for(int i=1;i<=N;i++){
            cin>>n[i];
            }
    for(int i=1;i<=N;i++){
            for(int j=1;j<=t;j++){
                    if(j<w[i]||n[i]==0){
                               f[i][j]=f[i-1][j];
                               continue;
                               }
                    for(int k=1;k<=n[i]&&k<=j/w[i];k++){
                            f[i][j]=max(f[i-1][j],f[i-1][j-k*w[i]]+k*v[i]);
                            }
                    
                    }
            }
    sort(f[6]+1,f[6]+1001); 
    int Total=0;
    for(int i=1;i<=1000;i++){
            if(f[6][i]!=f[6][i-1])
              Total++;
            }
    cout<<"Total="<<Total;
    return 0;
    }