0-1 背包问题
- 在 0-1 背包问题中,每种物品只能选择一次,因此一旦选择某个物品后,剩余的容量只能放入前面的物品。这就是为什么状态转移方程是:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w(i)] + v(i))
这里的 dp[i-1][j-w(i)] + v(i) 表示选择第 ( i ) 个物品后,剩余的容量只能放入前 ( i-1 ) 个物品。
// 如果是一维数组,0-1背包需要倒叙遍历保证每个物品只使用一次
for i:=0; i<len(物品); i++{
for j:=len(背包)+1; j>=weight[i]; j--{
dp[j] = max(dp[j], dp[j-weight[i]] + value(i))
}
}
完全背包问题
- 在完全背包问题中,每种物品可以重复放入多次,因此一旦选择某个物品后,剩余的容量仍然可以放入当前物品。这就是为什么状态转移方程是:
dp[i][j] = max(dp[i-1][j], dp[i][j-w(i)] + v(i))
这里的 dp[i][j-w(i)] + v(i) 表示选择第 ( i ) 个物品后,剩余的容量仍然可以放入第 ( i ) 个物品。
// 如果是一维数组,完全背包只需要变成正序遍历即可,因为每个物品都可以多次使用
// 先物品后背包,得出的是全组合,原因在于外层的物品是按照顺序便利的,所以 物品(2) 永远不会出现在物品(1) 前面
for i:=0; i<len(物品); i++{
for j:=0; j<len(背包)+1; j++{
dp[j] = max(dp[j], dp[j-weight[i]] + value(i))
}
}
// 先背包后物品得出的是全排列 物品=[1,2,3]
// 对于每一个背包容量,dp[2] = (1,1) + (2) = 2 种方式
// 然后到dp[3], 遍历物品1 dp[3] = dp[3] + dp[3-1] = 0 + 2 = 2 (1,1,1) (2,1) ,其实此处就可以看出可以倒叙了
// 遍历物品2 dp[3] = dp[3] + dp[3-2] = 2 + 1 = 3 (1,1,1) (2,1) (1,2) !! 最后一个(1,2)代表的是dp[0]的排列(1) ,加上此时遍历到的物品2,==> (1,2)
// 遍历物品3 dp[3] = dp[3] + dp[3-3] = 3 + 1 = 4 (1,1,1) (2,1) (1,2) (3) !! 此处其实也可以解释为什么dp[0]=1, 因为如果物品重量恰好等于背包容量,就必须有一种方法装入
for j:=0; j<len(背包)+1; j++{
for i:=0; i<len(物品); i++{
dp[j] = max(dp[j], dp[j-weight[i]] + value(i))
}
}
总结
- 0-1 背包:每个物品只能选一次,状态转移依赖于前一个状态。
- 完全背包:每个物品可以选多次,状态转移可以依赖于当前状态。
518 零钱找还
func change(amount int, coins []int) int {
// 完全背包相比与0-1背包不同的是,每个物品可以取无限次,所以在遍历物品时,要从前往后遍历
// dp五部曲
// dp数组以及下标含义 dp[i][j] 表示使用前j个物品转容量为i的背包能装的数量组合
// 递推公式 dp[i][j] = dp[i][j-w[i]] + dp[i-1][j] // 装i组合数量 + 不装i组合数量
// 初始化,装满背包0有1种方法, dp[0][0] = 1
// 遍历顺序,先物品后背包
// print
var dp = make([][]int, len(coins) + 1)
for idx, _ := range dp {
dp[idx] = make([]int, amount + 1)
}
dp[0][0] = 1
for i:=0; i<len(coins); i++ {
for j:=0; j<amount+1; j++{
if j - coins[i] >= 0 {
dp[i+1][j] = dp[i][j] + dp[i+1][j-coins[i]]
}else {
dp[i+1][j] = dp[i][j]
}
}
}
//fmt.Println(dp)
return dp[len(coins)][amount]
}
组合总和iv
func combinationSum4(nums []int, target int) int {
// 和零钱兑换解法一致, 多出来的一点在于需要判断不同的组合,由于二维数组不区分遍历顺序,所以只能使用先背包后物品的全排列
// dp五部曲
// dp数组以及下标含义 dp[j] 表示容量为j的背包能装满的数量排列
// 递推公式 dp[j] = dp[j-w[i]] + dp[j] // 装i组合数量 + 不装i组合数量
// 初始化,装满背包0有1种方法, dp[0] = 1
// 遍历顺序,先背包后物品
// print
var dp = make([]int, target + 1)
dp[0] = 1
for j:=1; j<=target; j++ {
for i:=0; i<len(nums); i++{
if j - nums[i] >= 0 {
dp[j] = dp[j] + dp[j-nums[i]]
}
}
}
//fmt.Println(dp)
return dp[target]
}
70 爬楼梯
func climbStairs(n int) int {
// 使用完全背包思路
// dp[j]表示装满容量j的背包排列数
// 递推 dp[j] = dp[j] + dp[j-w(j)]
// dp[0] = 1
// 遍历顺序 全排列完全背包 先正序背包 后正序物品
// print
var dp = make([]int, n+1)
dp[0] = 1
for j:=1; j<=n; j++ {
for i:=0; i<=2; i++{
if j>=i{
dp[j] = dp[j] + dp[j-i]
}
}
}
fmt.Println(dp)
return dp[n]
}
标签:背包,组合,int,day37,随想录,518,遍历,物品,dp
From: https://www.cnblogs.com/zhougongjin55/p/18373461