算法竞赛进阶指南， 281 页， 多重背包(此处代码抄书上的)
题目意思：
n种硬币，每种硬币的币值 A[i], 数量C[i], 给出一个数值m 求出可以拼成 1 ~ m 这 m种币值的哪几种？
本题要点：
1、 多重背包 的 “直接拆分法”，
bool f[MaxM]; //在阶段i， f[j] 表示前i种硬币是否能拼成面值j
在状态i（遍历到第i中硬币时候）
for(int k = m; k >= A[i]; --k) //币值 f[k] = f[k] | f[k - A[i]];{f[k] |= f[k - A[i]];}
2、 贪心策略
int used[MaxM]; //在阶段i, used[j] 表示 f[j]在阶段i 为true ，至少需要多少枚第i种硬币
在 i阶段， 面值j能够拼出来， 也就是f[j] == true的条件有2个：
1、 如果 f[j] 原来就是 true, 不进行状态转移，而且 used[j] == 0
2、 f[j] == false, 面值 j - A[i] 能够拼出来（f[j - A[i]] == true），
而且当前已经使用的 i 种硬币还有货可以用（used[j - A[i]] < C[i]）
if(!f[j] && f[j - A[i]] && used[j - A[i]] < C[i])
{f[j] = true;used[j] = used[j - A[i]] + 1;
}
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxM = 100010;
const int MaxN = 110;bool f[MaxM]; //在阶段i， f[j] 表示前i种硬币是否能拼成面值j
int used[MaxM]; //在阶段i, used[j] 表示 f[j]在阶段i 为true ，至少需要多少枚第i种硬币
int A[MaxN];
int C[MaxN];
int n, m;void solve()
{
memset(f, 0, sizeof(f));f[0] = true;for(int i = 1; i <= n; ++i){
for(int j = 0; j <= m; ++j){
used[j] = 0;}for(int j = A[i]; j <= m; ++j){
// 在 i阶段， 面值j能够拼出来， 也就是f[j] == true的条件有2个：// 1、 如果 f[j] 原来就是 true, 不进行状态转移，而且 used[j] == 0// 2、 f[j] == false, 面值 j - A[i] 能够拼出来，而且当前已经使用的 i 种硬币还有货可以用if(!f[j] && f[j - A[i]] && used[j - A[i]] < C[i]){
f[j] = true;used[j] = used[j - A[i]] + 1;}}}int ans = 0;for(int i = 1; i <= m; ++i){
ans += f[i];}printf("%d\n", ans);
}int main()
{
while(scanf("%d%d", &n, &m) != EOF && (n != 0 && m != 0)){
for(int i = 1; i <= n; ++i){
scanf("%d", &A[i]);}for(int i = 1; i <= n; ++i){
scanf("%d", &C[i]);}solve();}return 0;
}/* 3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0 *//* 8 4 */