最终实现代码如下：
int knap01(int N, int C, int w[], int v[]) { int *f = (int *)calloc(sizeof(int), C+1); int i, c; <span>for</span> (i = 0; i < N; i++) { <span>for</span> (c = C; c >= w[i]; c--) { f[c] = max(f[c], f[c-w[i]] + v[i]); } <span>printf</span>(<span>"%d: "</span>, i+1); <span>print</span>IntArray(f, C+1); // 打印f数组 } <span>return</span> f[C];}
复制代码
测试结果如下，即在背包容量为 10 的时候装第1和第2个物品(索引从0开始)，总重量为 4+5=9，最大价值为 5+6=11。
参数： w = [3, 4, 5] //物品重量列表 v = [4, 5, 6] //物品价值列表 C = 10 结果（打印数组f，i为选择的物品索引，c为背包重量，值为背包物品价值）： i/c 0 1 2 3 4 5 6 7 8 9 10 0: 0 0 0 4 4 4 4 4 4 4 4 1: 0 0 0 4 5 5 5 9 9 9 9 2: 0 0 0 4 5 6 6 9 10 11 11 KNap01 max: 11 复制代码初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0] 为 0 其它 f[1..C] 均设为 -∞，这样就可以保证最终得到的 f[N] 是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..C] 全部设为0。
为什么呢？可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的东西 “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
3.完全背包问题 问题描述有 N 种物品和一个容量为 C 的背包，每种物品都有无限件可用。第i种物品的重量是 w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大，物品不能只装部分。
基本思路这个问题非常类似于0-1背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件...等很多种。如果仍然按照解01背包时的思路，令 f[i][c] 表示前 i 种物品恰放入一个容量为 c 的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c } 复制代码这跟0-1背包问题一样有O(CN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态 f[i][c] 的时间是 O(c/w[i])，总的复杂度可以认为是 O(CN*Σ(c/w[i]))，是比较大的。实现代码如下：
/* * 完全背包问题 */ int knapComplete(int N, int C, int w[], int v[]) { int *f = (int *)calloc(sizeof(int), C+1); int i, c, k; for (i = 0; i < N; i++) { for (c = C; c >= 0; c--) { for (k = 0; k <= c/w[i]; k++) { f[c] = max(f[c], f[c-k*w[i]] + k*v[i]); } } printf("%d: ", i+1); printIntArray(f, C+1); } return f[C]; } 复制代码使用与0-1背包问题相同的例子，运行程序结果如下，最大价值为 13，即选取 2个重量3，1个重量4的物品，总价值最高，为 4*2 + 5 = 13。
i/c: 0 1 2 3 4 5 6 7 8 9 10 0: 0 0 0 4 4 4 8 8 8 12 12 1: 0 0 0 4 5 5 8 9 10 12 13 2: 0 0 0 4 5 6 8 9 10 12 13KNapComplete max: 13
复制代码
既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选 C/w[i] 件，于是可以把第 i 种物品转化为 C/w[i] 件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第 i 种物品拆成重量为 w[i]*2^k、价值为 w[i]*2^k 的若干件物品，其中 k 满足 w[i]*2^k<=C。这是二进制的思想，因为不管最优策略选几件第 i 种物品，总可以表示成若干个 2^k 件物品的和。这样把每种物品拆成 O(log C/w[i]) 件物品，是一个很大的改进。但我们有更优的 O(CN) 的算法。
进一步优化—O(CN)解法