题目描述

// 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

// 第 i 件物品的体积是 vi，价值是 wi。

// 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
// 输出最大价值。

算法1

Go 代码

package main

import "fmt"

const MAXN = 1005

var f [MAXN]int

func max(a int, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func main() {
    // n = 物品数量， m = 背包容量
    var n, m int
    fmt.Scan(&n, &m)
    // 如果大于物品数量，停止循环
    for i := 1; i <= n; i++ {
        // v = 物品体积，w = 价值
        var v, w int
        fmt.Scan(&v, &w)
        // 如果物品体积大于背包剩余容量，停止循环
        for j := m; j >= v; j-- {
            fmt.Println(f[j], f[j-v]+w)
            // 取放入价值最大的一组
            f[j] = max(f[j], f[j-v]+w)
        }
        fmt.Println(f[m])
    }
    fmt.Println(f[m])
}