完全背包就是有n个物品，第i（1<= i <= n）个物品的价值为v[i]，重量为w[i]，可以不限次数的选，问背包容量为m能装的最大价值。 先看看01背包怎么写：
for(int i = n;i >= 1;i--){ for(int j = m;j >= w[i];j--){ dp[j] = max(dp[j],dp[j-w[i]] + v[i]); } }这里只讲空间优化的情况：第二层for循环是倒叙的，因为第i个物品的状态只能由前一个转移，所以不能够由前往后更新，必须先更新后面的。
完全背包呢？01背包不能做的，完全背包可以做。一件物品可以选多次，其实只需要正序更新就好了，只要背包装的下，就可以再次选择这个物品。
for(int i = n;i >= 1;i--){ for(int j = w[i];j <= m;j++){ dp[j] = max(dp[j],dp[j-w[i]] + v[i]); } }和01背包差不多，只是每个物品有nun[i]个，所以转化为01背包求解。只是这样复杂度是m*∑(num[i])。
for(int i = n;i >= 1;i--){ for(int k = 1;k <= num[i];k++){ for(int j = m;j >= w[i];j--){ dp[j] = max(dp[j],dp[j-w[i]] + v[i]); } } }考虑优化：每个num[i]用二进制优化。 每个num[i]都可以拆成：1,2,4……,2^(k-1) , num[i] - 2 ^k +1。(k是num[i]-2 ^k +1 > 0的最大整数) 为什么可以这样拆分呢？证明： 显而易见1到2^(k-1) 的数, 可以构造出1到(2 ^k) - 1中的任何数。 那么2^k 到num[i]可以通过num[i] - 2 ^k +1 和前面构造出来的数来组，已知num[i]小于2 ^ (k+1)，设 t < 2 ^ k, 那么num[i] - t就是我们要构造的数，既然t已经小于等于2 ^ k - 1,那么t就可以被1到2 ^ (k-1)中的数字组成,而且num[i] - 2 ^ k + 1 <= 2 ^ k - 1 , 则1到num[i]所有的数字都可以被构造出来。（num[i] = 2 ^k - 1 + num[i] - 2 ^ k + 1）
int cnt = 0; for(int i = 1;i <= n;i++){ int j; for(j = 1;j <= num[i];j *= 2){//二进制优化 a[++cnt].v = v[i]; a[cnt].num = j; a[cnt].w = w[i]; num[i] -= j; } a[++cnt].v = v[i]; a[cnt].w = w[i]; a[cnt].num = num[i]; } for(int i = 1;i <= cnt;i++){ a[i].v *= a[i].num , a[i].w *= a[i].num; } for(int i = 1;i <= cnt;i++){ for(int j = m;j >= a[i].w;j--){ dp[j] = max(dp[j],dp[j-a[i].w] + a[i].v); } }复杂度为m*∑(log num[i])。 另外，如果每个num[i] 大于等于m/w[i]的话，可以转化成完全背包求解。
分组背包，就是把num[i]个物品分为一组，同一组中的物品互相冲突，最多选一个，问背包容量为m能装的最大价值。 分组背包和01背包也一样，只是需要换个含义。 定义dp[i][j]为前i组容量为j的最大价值。 然后当做01背包处理就好了，01的复杂度常数部分变为∑num[i] ， 总复杂度m*∑num[i]。
for(int i = 1;i <= n;i++){ dp[i][j] = dp[i-1][j]; for(int k = 1;k <= num[i];k++){ for(int j = m;j >= w[i][k];j--){ dp[i][j] = max(dp[i][j],dp[i-1][j-w[i][k]]+v[i][k]); } } }