1. 0-1背包问题

问题描述原题链接

一共有N件物品，第i（i从1开始）件物品的体积为w[i]，价值为w[i]。在总体积不超过背包上限V的情况下，能够装入背包的最大价值是多少?

解析

动态规划递推

d p [i] [j] = ma x (d p [i - 1] [j], d p [i - 1] [j - v [i]] + w [i])

代码

def solution(v:list, w: list, V: int, N: int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, V + 1):
            dp[i][j] = dp[i-1][j]
        	if j - v[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i])
    return dp[N][V]

1.1 一维优化

def solution(v:list, w: list, V: int, N: int):
    dp = [0] * (V + 1)
    for i in range(1, N + 1):
        for j in range(V, v[i]-1, -1): # 逆向枚举
            dp[j] = max(dp[j], dp[j-v[i]] + w[i])
    return dp[V]

完整代码：

def solution(v:list, w:list, V:int, N:int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, V + 1):
            dp[i][j] = dp[i-1][j]
            if j >= v[i]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i])
    return dp[N][V]
    
if __name__ == '__main__':
    N, V = map(int, input().split())
    v, w = [0] * (N + 1), [0] * (N + 1)
    for i in range(1, N + 1):
        v[i], w[i] = map(int, input().split())
    
    res = solution(v, w, V, N)
    print(res)

2. 完全背包问题

问题描述原题链接

有N种物品和一个容量是V的背包，[每种物品都有无限条件可用]。

第i种物品的体积是v[i], w[i]，求将哪些物品装入背包，可使这些物品总体积不超过背包容量，且总价最大。

代码

# 未优化代码
def solution(v:list, w:list, V:int, N:int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, V + 1):
            k = 0
            while j - k * v[i] >= 0:
                dp[i][j] = max(dp[i-1][j - k * v[i]] + k * w[i], dp[i][j])
                k += 1
    return dp[N][V]

2.1 二维优化

思路

三维优化为二维度的思路：

f [i] [j] = ma x (f [i - 1] [j], f [i - 1] [j - v] + w, f [i - 1] [j - 2 v] + 2 w, f [i - 1] [j - 3 v] + 3 w, .....) f [i] [j - v] = ma x (f [i - 1] [j - v], f [i - 1] [j - 2 v] + w, f [i - 1] [j - 3 v] + 2 w, .....)

由上两式，可得出如下递推关系：

f [i] [j] = ma x (f [i] [j - v] + w, f [i - 1] [j])

代码

def solution(v:list, w:list, V:int, N:int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, V + 1):
            dp[i][j] = dp[i-1][j]
            if j - v[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i][j-v[i]] + w[i])
                # 01背包的是：
                # dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i])
    return dp[N][V]

2.2 一维优化

代码

def solution(v:list, w:list, V:int, N:int):
    dp = [0] * (V + 1)
    for i in range(1, N + 1):
        for j in range(v[i], V + 1):  # 正序枚举
            dp[j] = max(dp[j], dp[j-v[i]] + w[i])
    return dp[V]

3. 多重背包问题

问题描述原题链接

有限数量的商品。有N种物品和一个容量是V的背包，第i种物品最多有s[i]件，每件体积是v[i],每件价值是w[i]。求最大价值

代码

def solution(v:list, w:list, s:list, V:int, N:int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1,V + 1):
            k = 0 
            while k <= s[i]:
                if j >= k*v[i]:
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]] + k*w[i])
                k += 1
    return dp[N][V]

3.1 二进制优化

原题链接

这一题不能使用类似于完全背包问题的方式进行优化。

f [i] [j] = ma x (f [i - 1] [j], f [i - 1] [j - v] + w, f [i - 1] [j - 2 v] + 2 w, ....., f [i - 1] [j - 3 v] + s w) f [i] [j - v] = ma x (f [i - 1] [j - v], f [i - 1] [j - 2 v] + w, ....., f [i - 1] [j - 3 v] + (s - 1) w, f [i - 1] [j - 3 v] + s w)

我们发现f[i][j-v]中比f[i][j]最后多了一项f[i-1][j-3v]+sw，不能直接得到这两者的关系，所以不能使用类似于完全背包问题的方式进行优化。

本次的优化方式为二进制优化，将s件物品进行拆分，然后可以转化成01背包问题

例如：

$s = 10$ , 10可以拆分为 $0 、 1 、 2 、 4 、 3$ ；
相当于将10个物品打包成4个物品，打包后的物品的体积和价值分别为单个物品的1、2、4、3倍；
这四个物品都是可选可不选，因此就转化成了01背包问题。

例如: $s = 200$

$200$ 可以拆分为 $0 、 1 、 2 、 4 、 8 、 16 、 32 、 64 、 73$ ；一共8个物品

总结：对于s，可以划分为 $l o g (s)$ 上取整个单一物品，然后用01背包问题的思路解决即可，时间复杂度： $O (N * V * l o g (s))$

为什么二进制的拆分是有效的？

任意一个实数可以由二进制数来表示，也就是 $[2^{0}, 2^{k}]$ 其中一项或几项的和

假如 $10$ 个取 $7$ 个，那么在实际的遍历过程中在第7个以后经过状态转移方程其实已经是选择“不取”好。现在，用二进制思想将其分堆，分成 $k + 1$ 个分别有 $2^{k}$ 个的堆，然后拿这一堆一堆去问，我是取了好呢，还是不取好呢，经过 $d p$ 选择之后，结果和拿一个一个来问的结果是完全一样的，因为dp选择的是最优结果，而根据任意一个实数都可以用二进制来表示，如果最终选出来10个取7个是最优的在分堆的选择过程中分成了 $2^{0}$ =1, $2^{1}$ =2, $2^{2}$ =4,10 - 7 = 3 这四堆，然后去问四次，也就是拿去走 $d p$ 状态转移方程，走的结果是第一堆1个，取了比不取好，第二堆2个，取了比不取好，第三堆四个，取了比不取好，第四堆8个，取了还不如不取，最后依旧是取了 $1 + 2 + 4 = 7$ 个。

代码

def solution(v:list, w:list, V:int, N: int):
    dp = [[0] * (V + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(1, V + 1):
            dp[i][j] = dp[i-1][j]
            if j >= v[i]:
                dp[i][j] = max(dp[i-1][j-v[i]]+w[i], dp[i][j])
    return dp[N][V]


if __name__ == "__main__":
    N, V = map(int, input().split())
    v, w, s = list(), list(), list()
    v.append(0)
    w.append(0)
    s.append(0)
    for i in range(1, N + 1):
        v_i, w_i, s_i = map(int, input().split())
        k = 1
        while k <= s_i:
            v.append(v_i * k)
            w.append(w_i * k)
            s_i -= k
            k <<= 1
        if s_i > 0:
            v.append(v_i*s_i)
            w.append(w_i*s_i)
    # 转化为01背包问题
    res = solution(v, w, V, len(v) - 1)
    print(res)

4. 混合背包问题

问题描述原题链接

有N种物品和一个容量为v的背包。物品一共有三类：

物品只能用一次(01背包)
物品可以用无限次（完全背包）
最多只能用s次(多重背包)

每种物品的体积是v，价值是w

求解将哪些物品装入背包，可以使得物品体积不操过背包容量，且价值总和最大。

输入描述

第一行：两个整数， $N$ ， $V$ ，用空格隔开，分别表示物品种数和背包容积

接下来的 $N$ 行：输入三个整数 $v$ ， $w$ , $s$ 用空格隔开，分别表示第i种物品的体积，价值，数量。

$s = - 1$ 表示物品只能用1次
$s = 0$ 表示物品可以用无限次
$s > 0$ 表示物品可以使用s次

def solution(v: list, w: list, s: list, V):
    n = len(v)
    f = [0] * (V + 1)
    for i in range(n):
        if s[i] == 0:  # 完全背包
            for j in range(v[i], V + 1): # 正向枚举
                f[j] = max(f[j], f[j-v[i]] + w[i])
        else:  # 全部转换为多重背包，然后使用二进制优化
            if s[i] == -1:
                s[i] = 1
            k = 1
            while k <= s[i]:
                for j in range(V, k * v[i] - 1, -1):
                    f[j] = max(f[j], f[j-k*v[i]] + k*w[i])
                s[i] -= k
                k <<= 1
            if s[i] > 0:
                for j in range(V, s[i] * v[i]-1, -1):
                    f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i])
    return f[V]


if __name__ == '__main__':
    N, V = map(int, input().split())
    v, w, s = [0] * N, [0] * N, [0] * N
    for _i in range(N):
        v[_i], w[_i], s[_i] = map(int, input().split())
    res = solution(v, w, s, V)
    print(res)

5. 二维费用背包问题

问题描述

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vivi，重量是 m，价值是 w。

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

输入格式

第一行三个整数，N,V,M 用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 NN 行，每行三个整数 v,m,w 用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

分析

需要说明一点，二维费用背包为可以和 01背包、完全背包、多重背包、分组背包 这四种类型背包中的任何一种组合起来。
当前题目是和 01背包 绑定起来的题目

代码实现

def solution(v, w, m, V, M):
    f = [[0] * (M + 1) for _ in range(V + 1)]  # 第一维代表体积，第二维代表重量
    n = len(v)
    for i in range(n):
        for j in range(V, v[i] - 1, -1):  # 01 背包
            for k in range(M,  m[i] - 1, -1):
                f[j][k] = max(f[j][k], f[j-v[i]][k-m[i]] + w[i])
    return f[V][M]


if __name__ == '__main__':
    N, V, M = map(int, input().split())
    v, w, m = [0] * N, [0] * N, [0] * N
    for i in range(N):
        v[i], m[i], w[i] = map(int, input().split())
    res = solution(v, w, m, V, M)
    print(res)

6. 分组背包问题

问题描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{ij}$ ，价值是 $w_{ij}$ ，其中 $i$ 是组号， $j$ 是组内编号。

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

输出最大价值。

输入格式

第一行有两个整数 N，V用空格隔开，分别表示物品组数和背包容量。

接下来有 N组数据：

每组数据第一行有一个整数 $S_{i}$ ，表示第 i 个物品组的物品数量；
每组数据接下来有 $S_{i}$ 行，每行有两个整数 $v_{ij}$ , $w_{ij}$ 用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围
$1 \leq N, V \leq 100$
$1 \leq v_{i}, w_{i} \leq 100$

父节点编号范围：

内部结点： $1 \leq p_{i} \leq N$ ;
根节点 $p_{i} = - 1$ ;

c++

#include <iostream>
#include <vector>
using namespace std;
int f[110][110];  // f[x][v] 表达选择以x为子树的物品，在容量不超过v时所获得的最大价值
vector<int> g[110];
int v[110], w[110];
int n, m, root;

int dfs(int x){
    for(int i = v[x]; i<=m; i++) f[x][i] = w[x];
    for(int i=0; i<g[x].size(); i++){
        int y = g[x][i];
        dfs(y);
        for(int j=m; j>=v[x]; j--){
            for(int k=0; k<=j-v[x]; k++){
                f[x][j] = max(f[x][j], f[x][j-k] + f[y][k]);
            }
        }
    }
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        int fa;
        cin >>v[i]>>w[i]>>fa;
        if(fa == -1) root = i;
        else g[fa].push_back(i);
    }
    dfs(root);
    cout<<f[root][m];
    return 0;
}