n个物品，m为最大体积，v[i]、w[i]、s[i]：物品i的体积、价值和数量

朴素版本

f[i][j] = Max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]), k=0,1,2,...,s[i]

package main

import "fmt"

const N = 110
var n, m int
var v, w, s [N]int
var f [N][N]int
func main(){
    fmt.Scan(&n, &m)

    for i:=1; i<=n; i++{
        fmt.Scan(&v[i], &w[i], &s[i])
    }

    for i:=1; i<=n; i++{
        for j:=0; j<=m; j++{
            for k:=0; k<=s[i] && k*v[i]<=j; k++{
                f[i][j] = maxInt(f[i][j], f[i-1][j-k*v[i]] + k*w[i])
            }
        }
    }

    fmt.Println(f[n][m])
}
func maxInt(a, b int)int{
    if a > b {
        return a
    }
    return b
}

二进制优化

采用倍增的思想，将若干个i物品进行打包分组，比如第一组只有1个i物品，第二组有2个i物品，…
每个组只能使用0或者1次，那么s[i]一定可以被这些组表示出来。

这样就可以使用01背包的思想进行优化，

package main

import "fmt"

const M = 2010
const N = 12010 //最多1000组，每组最多分成log(2000) 上取整12 所以最大有12000个
var n, m int
var v, w [N]int
var f [M]int
func main(){
    fmt.Scan(&n, &m)
    cnt := 0
    var a, b, s int
    for i:=1; i<=n; i++{
        fmt.Scan(&a, &b, &s)
        k := 1
        for k <= s{
            cnt++
            v[cnt] = a * k
            w[cnt] = b * k
            s -= k
            k *= 2
        }
        if s > 0{
            cnt++
            v[cnt] = a * s
            w[cnt] = b * s
        }
    }
    //全部的分组数
    n = cnt

    //使用01背包的方式
    for i:=1; i<=n; i++{
        for j:=m; j>=v[i]; j--{
            f[j] = maxInt(f[j], f[j-v[i]] + w[i])
        }
    }
    fmt.Println(f[m])
}
func maxInt(a, b int)int{
    if a > b {
        return a
    }
    return b
}