完全背包问题是01背包问题的升级版，它的主要改变是在物品的数量从1变成了多个。
题目
有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的耗费空间是 Ci ，价值是 Wi 。求将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大
题目分析
按照上一篇文章对01背包问题的解析，我们可以得到状态转移方程：F[i, v] = max{F[i − 1, v − kCi] + kWi | 0 ≤ kCi ≤ v}。但是这个状态转移方程的时间复杂度达到O(NVΣVCi)，所以我们必须进行一定的优化。
实际上，我们在上篇文章的方法二基础上进行一定的改动，即把 v 的循环次序从逆序改为正序，即可解决问题。这是因为01背包中让 v 递减是为了保证第 i 次循环中的状态 F[i, v] 是由状态 F[i − 1, v − Ci] 递推而来，即保证每件物品只选一次，而完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却正需要一个可能已选入第 i 种物品的子结果 F[i, v − Ci] ，所以须采用 v 递增的顺序循环。在这种方法中，状态转移方程为：F[v] = max{F[v], f[v − C] + W}。
实现代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, v;
int *c, *w;
int *f;
int main() {
while(scanf("%d%d", &n, &v) == 2) {
c = (int *)malloc(sizeof(int) * (n + 1));
w = (int *)malloc(sizeof(int) * (n + 1));
f = (int *)malloc(sizeof(int) * (v + 1));
memset(f, 0, (v + 1) * sizeof(int));
for(int i = 1; i <= n; i++) {
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = c[i]; j <= v; j++) {
f[j] = f[j] > f[j - c[i]] + w[i] ? f[j] : f[j - c[i]] + w[i];
}
}
printf("%d\n", f[v]);
}
return 0;
}