算法竞赛进阶指南，277页，01背包
本题要点： 1、把01背包的代码改改即可。常规的01背包： 有n个背包，每个物品的体积是v[i], 价值是w[i]， 求装到大小为m的大背包，能获得的最大价值。 f[j]表示到小为i的背包，最多能获得的最大价值 f[j] = max(f[j], f[j - v[i]] + w[i]); 2、题目意思转换： 有n个背包，每个物品的体积是v[i], 价值是1， 求装到大小为m的大背包，一共有多少种装法。 f[j]表示到小为i的背包, 一共有多少种装法： f[j] = f[j] + f[j - v[i]]; //不装第i个物品，装第i个物品
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int MaxN = 10010; int v[MaxN], w[MaxN]; //体积重量 int f[MaxN]; //f[i] 和为i有多少种方案 int a[MaxN]; int n, m; void solve() { memset(f, 0, sizeof f); f[0] = 1; for(int i = 1; i <= n; ++i) { for(int j = m; j >= v[i]; --j) { f[j] = f[j] + f[j - v[i]]; //不装第i个物品，装第i个物品 } } printf("%d\n", f[m]); } int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%d", &v[i]); w[i] = 1; } solve(); return 0; } /* 4 4 1 1 2 2 */ /* 3 */