这个问题取自ACWing网站，共有9题，今天记录两题
package main
import (
"fmt"
)
// 完全背包 一维
func testCompletePackOneDimesional() {
var result [100]int
var maxCount, maxVolume int
fmt.Println("请输入两个整数（空格分隔）前者是个数，后者是容量上限：")
fmt.Scan(&maxCount, &maxVolume)
for i := 1; i <= maxCount; i++ {
var objVolume, objQuality int
fmt.Println("请输入两个整数，前者代表质量，后者代表体积")
fmt.Scan(&objVolume, &objQuality)
for j := objVolume; j <= maxVolume; j++ {
result[j] = max(result[j], result[j-objVolume]+objQuality)
}
}
fmt.Println(result[maxVolume])
}
// 完全背包去掉k曾
func testCompletePackDeleteK() {
// maxQuality
var result [100][100]int
var maxCount, maxVolume int
fmt.Println("请输入两个整数（空格分隔）前者是个数，后者是容量上限：")
fmt.Scan(&maxCount, &maxVolume)
for i := 1; i <= maxCount; i++ {
var objVolume, objQuality int
fmt.Println("请输入两个整数，前者代表质量，后者代表体积")
fmt.Scan(&objVolume, &objQuality)
for j := objVolume; j <= maxVolume; j++ {
result[i][j] = max(result[i-1][j], result[i][j-objVolume]+objQuality)
}
// fmt.Println(result[i][maxVolume])
}
fmt.Println(result[maxCount][maxVolume])
}
// 完全背包
// 完全背包理解就是 先把第一种物品拿满（指体积上限），就是全部都拿第一种
// 然后去拿第二种，如果第二种不划算（说白了就是相比第一种价值/体积的值更小），
// k = 0的时候，result[i][j] 初始值是0
// 经过max(result[i][j], result[i-1][j-k*objVolume]+k*objQuality) ，result[i][j] 必然是 result[i -1][j]
// k=1 时max(result[i][j], result[i-1][j-k*objVolume]+k*objQuality)的时候选择了
// 理解成将第一种去掉一个，换成第二种看看是否价值更高
// 如果总价值更高，后面只会不断的把第一种去掉换成第二种
// 如果总价值低了，那么说白了，对于第二种而言，后面的
// max(result[i][j], result[i-1][j-k*objVolume]+k*objQuality)都会是result[i – i][j]
func testCompletePack() {
// maxQuality
var result [100][100]int
var maxCount, maxVolume int
fmt.Println("请输入两个整数（空格分隔）前者是个数，后者是容量上限：")
fmt.Scan(&maxCount, &maxVolume)
for i := 1; i <= maxCount; i++ {
var objVolume, objQuality int
fmt.Println("请输入两个整数，前者代表质量，后者代表体积")
fmt.Scan(&objVolume, &objQuality)
for j := objVolume; j <= maxVolume; j++ {
for k := 0; k*objVolume <= j; k++ {
result[i][j] = max(result[i][j], result[i-1][j-k*objVolume]+k*objQuality)
}
}
// fmt.Println(result[i][maxVolume])
}
fmt.Println(result[maxCount][maxVolume])
}
// 0 1 背包优化 一维
func test01packonedimensional() {
var result [100]int
var a, b int
fmt.Println("请输入两个整数（空格分隔）前者是个数，后者是容量上限：")
fmt.Scan(&a, &b)
fmt.Printf("a=%d, b=%d\\n", a, b)
for i := 1; i <= a; i++ {
var c, d int
fmt.Println("请输入两个整数，前者代表质量，后者代表体积")
fmt.Scan(&c, &d)
for j := b; j >= c; j– {
result[j] = max(result[j], result[j-c]+d)
}
}
fmt.Println(result[b])
}
// 0 1 背包
func test01pack() {
var result [100][100]int
var a, b int
fmt.Println("请输入两个整数（空格分隔）前者是个数，后者是容量上限：")
fmt.Scan(&a, &b)
fmt.Printf("a=%d, b=%d\\n", a, b)
for i := 1; i <= a; i++ {
var c, d int
fmt.Println("请输入两个整数，前者代表质量，后者代表体积")
fmt.Scan(&c, &d)
for j := b; j >= c; j– {
result[i][j] = max(result[i-1][j], result[i-1][j-c]+d)
}
}
fmt.Println(result[a][b])
}
func max[T ~int | ~int8](x, y T) (a T) {
if x > y {
return x
}
return y
}
func main() {
// 01 背包
// test01pack()
// test01packonedimensional()
// 完全背包
// testCompletePack()
testCompletePackDeleteK()
// testCompletePackOneDimesional()
}
然后配一个图片，是完全背包的 去掉k层的推理过程
