题目链接：https://www.luogu.org/problemnew/show/P2347
题目描述
设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
输入输出格式
输入格式：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出格式：
输出方式：Total=N
（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）
输入输出样例
输入样例#1：
1 1 0 0 0 0
输出样例#1：
Total=3 解题思路：
先打一个b[10]={0,1,2,3,5,10,20}；再用a数组记录展开后的a1个1g，a2个2g。。将多重背包转化为01背包问题
比如：2 1 2 1 1 1存在a里就是1 1 2 3 3 5 10 20 ；
a数组里元素个数为a1~a6的和，记为num
从1到num扫一遍，把所有可能出现的情况在一个f数组中标记出来；
最后从1000到0跑一遍，找到的一个非零的值ans++；跑完之后ans即为所有情况数；
#include<bits/stdc++.h>
using namespace std;
]; //f数组存放第k+w[i]种重量有没有被称出来过
], w[] = { ,,,,,, };
int main() {
; i <= ; i++)
scanf("%d", &a[i]);
memset(f, , sizeof(f));
f[] = ;
; i <= ; i++) //对砝码的种类进行枚举
; j <= a[i]; j++) // 每一种相同质量的砝码个数进行枚举
; k >= ; k--) { //k表示当前重量
)
f[k + w[i]] = ; //如果第k+w[i]个没有称出来过就标记上
}
;
; i <= ; i++) //注意这里从1开始,因为题目要求不包含一个砝码也不用的情况
{
if (f[i]) ans++;
}
printf("Total=%d", ans);
;
}
2018-05-14