- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=100,000），要求：计算用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况。
- 输入
- 一行，包括六个正整数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三种不同的重量。
-
转化成多重背包类型的就可以了
#include<bits/stdc++.h>
using namespace std;
int a[];
int h[];
bool f[];
int ans;
int sum;
int main(){
a[]=; a[]=; a[]=; a[]=; a[]=; a[]=;
for(int i=;i<=;i++) scanf("%d",&h[i]),sum+=a[i]*h[i];
f[]=true;
for(int i=;i<=;i++){
for(int v=sum;v>;v--){
for(int k=;k<=h[i];k++){
if(k*a[i]<=v&&f[v-k*a[i]]==true){
f[v]=true;
}
}
}
}
for(int i=;i<=sum;i++){
if(f[i]==true) ans++;
}
cout<<"Total="<<ans;
return ;
}