算法训练营day38(补)，动态规划6
package main
func max(a, b int) int {
if a > b {
return a
}
return b
}
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
每件商品都有无限个！
问背包能背的物品最大价值是多少？
func package03(weight, value []int, bagweight int) int {
dp := make([]int, bagweight+1)
//遍历物品
for i := 0; i < len(weight); i++ {
//遍历背包容量
for j := weight[i]; j <= bagweight; j++ {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
return dp[bagweight]
}
//518. 零钱兑换 II
//求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for i := 0; i < len(coins); i++ {
for j := coins[i]; j <= amount; j++ {
dp[j] += dp[j-coins[i]]
}
}
return dp[amount]
}
//377. 组合总和 Ⅳ
func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for j := 0; j <= target; j++ {
for i := 0; i < len(nums); i++ {
if j >= nums[i] {
dp[j] += dp[j-nums[i]]
}
}
}
return dp[target]
}