DP的背包问题小结-java语言描述
依然是复习以前学过的内容hhh
一、01背包
题目
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
分状态和转移方程
显然变量为装入的物品和背包的质量，所求的目标是最大的价值。
因此设dp[i][j]来表示将前i件物品在j的限重下的价值最大值。
对于每个状态dp[i][j]有两种情况：
装入第i件物品（
dp[i-1][j-w[i]] + v[i]）不装入 （
dp[i-1][j]）
故转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
二、完全背包
题目
同01背包类似，但每种物品可以取无限个。
分析
和01背包类似，我们设出同样的dp状态，dp[i][j]来表示将前i种物品在j的限重下的价值最大值。
还是分两种情况：
装入第i种物品，但和01背包不一样，这里装入一次以后还可以继续装入，所以应该转移到
dp[i][j-w[i]] + v[i]而不是dp[i-1][j-w[i]] + v[i]。不装入第i种物品（还是
dp[i-1][j]）
所以转移方程为：
dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])
优化
这里可以做一个优化，可以通过滚动数组的方式，省去[i]，压缩空间复杂度。
转移方程可改写为：dp[j] = max(dp[j], dp[j-w[i]] + v[i])
这里注意时间复杂度是不能被压缩的，而且这样写的前提是循环时j必须正向枚举，确保此时访问的dp[j-[i]]已经在本次循环中被计算到。
01背包也可以类似优化，只不过要逆向枚举，确保此时访问的
dp[j-[i]]是上一次循环计算到的结果。
三、多重背包
题目
和完全背包不一样在于每种物品的数量是指定好的。一共有N种物品，第i（i从1开始）种物品的数量为n[i]，重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
分析
因为指定了特定种类的物品数就相当于指定了n个独立的物品，所以多重背包问题可以直接化为01背包问题解决，其时间复杂度也不高。
转移方程可参考01背包。具体就是把给定数量的物品都视为单独的01背包里的物品来处理。
参考
最后更新于