算法训练营day36(补)，动态规划4
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
func max(a, b int) int {
if a > b {
return a
}
return b
}
//二维数组解法
func package01(weight, value []int, bagweight int) int {
// weight表示物品重量 value表示物品价值, bagweight背包容量
dp := make([][]int, len(weight))
for i, _ := range dp {
dp[i] = make([]int, bagweight+1)
}
for i := bagweight; i >= weight[0]; i-- {
dp[0][i] = dp[0][i-weight[0]] + value[0]
}
for i := 1; i < len(weight); i++ {
for j := 0; j <= bagweight; j++ {
// 当前物品weight[i]重量大于背包重量j,此时不能再放物品，他的最大价值就是dp[i-1][j]
if j < weight[i] {
dp[i][j] = dp[i-1][j]
} else {
//否则判断背包减去当前物品weight[i]重量+当前物品价值，和之前价值取最大值
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
}
}
}
return dp[len(weight)-1][bagweight]
}
//一维数组解法
func package02(weight, value []int, bagweight int) int {
dp := make([]int, bagweight+1)
for i := 0; i < len(weight); i++ {
///这里必须倒序,区别二维,因为二维dp保存了i的状态
for j := bagweight; j >= weight[i]; j-- {
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
}
}
return dp[bagweight]
}
func canPartition(nums []int) bool {
sum := 0
n := len(nums)
for i := 0; i < n; i++ {
sum += nums[i]
}
if sum%2 != 0 {
return false
}
mid := sum / 2
dp := make([]int, mid+1)
for i := 0; i < n; i++ {
///这里必须倒序
for j := mid; j >= nums[i]; j-- {
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
}
}
return dp[mid] == mid
}
原文地址：https://blog.csdn.net/weixin_50253985/article/details/136310303
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！