背包九讲(超值得看的一大坨资料，附代码、视频、资料...)

刷算法题必懂的思想，包含01背包问题、完全背包问题、多重背包问题、混合背包、二维费用的背包问题、分组背包问题、背包问题求方案数、求背包问题的方案；看完后悔你捶我！

未名湖畔种千玺

2126人浏览 · 2021-04-05 12:22:41

未名湖畔种千玺 · 2021-04-05 12:22:41 发布

背包九讲概述

1. 01背包问题

题目

01背包问题

每件物品只能选0次或者1次
在这里插入图片描述

2. 完全背包问题

题目

完全背包问题

每件物品可以选无数次
在这里插入图片描述

3. 多重背包问题

题目

多重背包问题 I

限定每件物品的数量
在这里插入图片描述

4. 混合背包问题

题目

混合背包问题

有的物品只能选一次，有的可以选无限次，有的可以选n次
在这里插入图片描述

5. 二维费用的背包问题

题目

二维费用的背包问题

物品拥有体积质量和价值
在这里插入图片描述

6. 分组背包问题

题目

分组背包问题

若干组物品，每一组只能选一个

在这里插入图片描述

7. 背包问题求方案数

题目

背包问题求方案数

最优解的数量

在这里插入图片描述

8. 求背包问题的方案

题目

背包问题求具体方案

输出最优方案

在这里插入图片描述

9. 有依赖的背包问题

如果选择某个物品，就必须先选择他的父节点物品

10、用最少的物品填满背包

题目

322. 零钱兑换

用最少的物品填满背包
在这里插入图片描述

1、01背包

动态规划DP0-1背包

理解

思路

首先要理解：
f(k,w):当背包容量为w，现有k件物品可以偷，所能偷盗的最大价值

01背包是后面八种背包的基础，搞清楚01背包后面八种背包一看就会！！！！

谨记一句话：一句话先循环物品再循环体积再循环决策

在这里插入图片描述

代码实现

代码


package com.review.backpack_01;

public class BP01 {
    //01背包问题
    //每件物品只能选0次或者1次
    private int maxValue(int[] weight, int[] value, int bagWeight) {//常规做法
        // dp[i][j]的含义是：可选物品为i，背包容量是j时背包的最大价值
        // new int[weight.length][bagWeight + 1]为什么是bagWeight + 1呢？
        // 因为j代表的背包的真实容量，但是数组是从0开始的
        int[][] dp = new int[weight.length][bagWeight + 1];

        // 因为dp[0][j]中的0对应的是第一件物品，所以dp[0][j]的含义是可选物品为1，背包容量为j；
        // 当j大于等于weight[0]此时背包最大价值就是value[0]也就是第一件物品的价值
        for (int j = bagWeight; j >= weight[0]; j--) {
            dp[0][j] = value[0];
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }

    private int maxValue2(int[] weight, int[] value, int bagWeight) {//改进做法，使用一维数组

        int[] dp = new int[bagWeight + 1];

        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        System.out.println("常规做法，使用二维数组：" + new BP01().maxValue(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
        System.out.println("改进做法，使用一维数组：" + new BP01().maxValue2(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}

运行结果

常规做法，使用二维数组：35
改进做法，使用一维数组：35

Process finished with exit code 0

2、完全背包

在这里插入图片描述

代码实现

package com.review.backpack_01;

public class BP02 {
    //2. 完全背包问题
    //每件物品可以选无数次
    private int maxValue(int[] weight, int[] value, int bagWeight) {//改进做法
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = weight[i]; j <= bagWeight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        return dp[dp.length - 1];
    }

    private int maxValue2(int[] weight, int[] value, int bagWeight) {//常规做法
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                for (int k = 0; k * weight[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        System.out.println("常规做法：" + new BP02().maxValue2(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
        System.out.println("改进做法：" + new BP02().maxValue(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}

运行结果

常规做法：60
改进做法：60

Process finished with exit code 0

3、多重背包

在这里插入图片描述

代码实现

package com.review.backpack_01;

public class BP03 {
    //3. 多重背包问题
    //限定每件物品的数量
    private int maxValue(int[] weight, int[] value, int[] num, int bagWeight) {

        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {//前半部分和01背包相同
                for (int k = 1; k <= num[i] && k * weight[i] <= j; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        return dp[dp.length - 1];
    }

    //优化
    private int maxValue2(int[] weight, int[] value, int[] num, int bagWeight) {

        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++) {
            int s = num[i];
            for (int j = 1; j <= s; s -= j, j <<= 1) {
                for (int k = bagWeight; k >= 0 && k >= weight[i] * j; k--) {
                    dp[k] = Math.max(dp[k], dp[k - j * weight[i]] + j * value[i]);
                }
            }
            if (s > 0) {
                for (int j = bagWeight; j >= s * weight[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - s * weight[i]] + s * value[i]);
                }
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(new BP03().maxValue(new int[]{1, 2, 3, 4}, new int[]{2, 4, 4, 5}, new int[]{3, 1, 3, 2}, 5));//10
        System.out.println(new BP03().maxValue2(new int[]{1, 2, 3, 4}, new int[]{2, 4, 4, 5}, new int[]{3, 1, 3, 2}, 5));//10

    }
}

运行结果

10
10

Process finished with exit code 0

4、混合背包

代码实现

package com.some;

import com.review.backpack_01.BP04;

public class BP04_test {
    /*
    混合背包
    p=−1  表示第 i 种物品只能用1次；
    p=0 表示第 i 种物品可以用无限次；
    p>0 表示第 i 种物品可以使用 p 次；
     */
    public static int knapsackProblem(int[] w, int[] v, int[] p, int cap) {
        int[] dp = new int[cap + 1];

        for (int i = 0; i < w.length; i++) {

            if (p[i] == -1) {
                // 01背包
                for (int j = cap; j >= w[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            } else if (p[i] == 0) {
                // 完全背包
                for (int j = w[i]; j <= cap; j++) {
                    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
                }
            } else {
                // 多重背包
                for (int j = cap; j >= w[i]; j--) {
                    for (int k = 0; (k <= p[i]) && (k * w[i] <= j); k++) {
                        dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
                    }
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        System.out.println(
                knapsackProblem(
                        new int[]{2, 3, 4, 5, 6, 7, 8},
                        new int[]{3, 4, 5, 6, 7, 8, 9},
                        new int[]{1, 1, 0, 0, 1, 3, 4}, 27
                )
        );
        System.out.println(
                knapsackProblem(
                        new int[]{1, 2, 3, 4},
                        new int[]{2, 4, 4, 5},
                        new int[]{-1, 1, 0, 2}, 5
                )
        );

    }
}

运行结果

34
8

Process finished with exit code 0

5、二维费用的背包问题

代码实现

package com.review.backpack_01;

public class BP05 {
    //5. 二维费用的背包问题
    //物品拥有体积质量和价值
    public int knapsackProblem(int[] volume, int maxV, int[] weight, int maxW, int[] value) {
        int[][] dp = new int[maxV + 1][maxW + 1];
        for (int i = 0; i < volume.length; i++) {
            for (int j = maxV; j >= volume[i]; j--) {
                for (int k = maxW; k >= weight[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - volume[i]][k - weight[i]] + value[i]);
                }
            }
        }
        return dp[maxV][maxW];
    }

    public static void main(String[] args) {
        System.out.println(
                new BP05().knapsackProblem(
                        new int[]{1, 2, 3, 4},
                        5,
                        new int[]{2, 4, 4, 5},
                        6,
                        new int[]{3, 4, 5, 6}
                )
        );
    }
}

运行结果

8

Process finished with exit code 0

6、分组背包问题

代码实现

package com.review.backpack_01;

public class BP06 {
    //6. 分组背包问题
    //若干组物品，每一组只能选一个
    public int knapsackProblem(int[][] c, int[][] v, int cap) {
        int[] dp = new int[cap + 1];
        
        for (int i = 0; i < c.length; i++) {
            for (int j = cap; j >= 0; j--) {// 确保每个组中至多只有一个物品被选择
                for (int k = 0; k < c[i].length; k++) {
                    if (j >= c[i][k]) {
                        dp[j] = Math.max(dp[j], dp[j - c[i][k]] + v[i][k]);
                    }
                }
            }
        }
        return dp[cap];
    }

    public static void main(String[] args) {
        System.out.println(
                new BP06().knapsackProblem(
                        new int[][]{{1, 2, 3}, {2, 3, 4}, {5, 6, 7, 8}, {7, 9}},
                        new int[][]{{2, 3, 4}, {1, 2, 3}, {4, 5, 6, 7}, {8, 9}},
                        11
                )
        );
    }
}

运行结果

12

Process finished with exit code 0

7、背包问题求方案数

AcWing 11. Java-背包问题求方案数—注释版代码

代码实现

package com.review.backpack_01;

import java.util.Arrays;

public class BP07_2 {
    //7. 背包问题求方案数
    //最优解的数量
    //在01背包里加入判断

    public static int knapsackProblem(int[] c, int[] v, int V) {
        int[] dp = new int[V + 1];
        int[] count = new int[V + 1];

        // 初始化，此时的count代表i=0，即没有物品可以选择时
        // 什么都不选，也是一种方案
        Arrays.fill(count, 1);

        for (int i = 0; i < c.length; i++) {
            for (int j = V; j >= c[i]; j--) {
                if (dp[j] < dp[j - c[i]] + v[i]) {
                    // 选择当前物品的收益要高，因此这里dp的选择必然是选择当前物品，
                    // 因为是必然，所以这样的方案数量不变
                    count[j] = count[j - c[i]];
                } else if (dp[j] == dp[j - c[i]] + v[i]) {
                    // 二者的收益相等，这里可以选，也可以不选
                    // 因此这里是加上count[j-v[i]]
                    count[j] += count[j - c[i]];
                } else {
                    // 不选的收益更高，那么这里dp的选择必然是不选
                    // 因此保持count[n-1][j]即可
                }
                dp[j] = Math.max(dp[j], dp[j - c[i]] + v[i]);
            }
        }
        return count[V];
    }

    public static int knapsackProblem_2(int[] c, int[] v, int V) {
        int[][] dp = new int[c.length + 1][V + 1];
        int[][] count = new int[c.length + 1][V + 1];

        // 初始化，此时的count代表i=0，即没有物品可以选择时
        // 什么都不选，也是一种方案
        for (int[] ints : count) {
            Arrays.fill(ints, 1);
        }


        for (int i = 1; i < c.length; i++) {
            for (int j = 0; j <= V; j++) {
                if (j >= c[i]) {
                    // 背包容量大于当前物品容量
                    if (dp[i - 1][j] < dp[i - 1][j - c[i]] + v[i]) {
                        // 选择当前物品的收益更高
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j - c[i]] + v[i];
                        // 当前方案只是在之前方案的基础上加了当前的物品，因此方案数量不变
                        count[i][j] = count[i - 1][j - c[i]];

                    } else if (dp[i - 1][j] == dp[i - 1][j - c[i]] + v[i]) {
                        // 两种办法收益相等
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j];
                        // 当前方案有两种选择，一是不增加当前物品，二是增加当前物品，所以方案数量等于二者之和
                        count[i][j] = count[i - 1][j] + count[i - 1][j - c[i]];
                    } else {
                        // 选择当前物品的收益更高
                        // 更新当前收益
                        dp[i][j] = dp[i - 1][j];
                        // 当前方案不增加物品，与之前的方案等同
                        count[i][j] = count[i - 1][j];
                    }
                } else {
                    // 背包容量下雨当前物品容量
                    dp[i][j] = dp[i - 1][j];
                    count[i][j] = count[i - 1][j];
                }

            }
        }
        return count[c.length][V];
    }

    public static void main(String[] args) {
        System.out.println(knapsackProblem(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
        System.out.println(knapsackProblem_2(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}

运行结果

1
1

Process finished with exit code 0

8、求背包问题的方案

代码实现

package com.review.backpack_01;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class BP08_2 {
    //8. 求背包问题的方案
    //输出最优方案
    public static int knapsackProblem(int[] c, int[] v, int cap) {
        // 记录最大价值
        int[][] dp = new int[c.length][cap + 1];
        // 记录当前物品是否被选择
        int[][] choose = new int[c.length][cap + 1];

        for (int i = cap; i >= c[0]; i--) {
            dp[0][i] = v[0];
            choose[0][i] = 1;
        }
        for (int i = 1; i < c.length; i++) {
            for (int j = 1; j <= cap; j++) {
                if (j >= c[i]) {
                    if (dp[i - 1][j] <= dp[i - 1][j - c[i]] + v[i]) {
                        // 选择当前物品为最优解
                        dp[i][j] = dp[i - 1][j - c[i]] + v[i];
                        choose[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        // 反推出物品编号
        List<Integer> list = new LinkedList<>();
        int i = c.length - 1, V = cap;
        while (i >= 0) {
            if (choose[i][V] != 0) {
                list.add(i);
                V -= c[i];
            }
            i--;
        }
        Collections.reverse(list);
        System.out.println("最优方案选择：" + list);

        return dp[dp.length - 1][dp[0].length - 1];
    }

    public static void main(String[] args) {
        System.out.println(knapsackProblem(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4));
    }
}

运行结果

最优方案选择：[0, 1]
35

Process finished with exit code 0

10、用最少的物品填满背包

代码实现

import java.util.Arrays;

public class BP10 {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == (amount + 1) ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }
}

运行结果

3

Process finished with exit code 0

资料引用

网上资料

背包问题九讲

https://ishare.iask.sina.com.cn/f/17570695.html

背包九讲 2.0.pdf

https://max.book118.com/html/2017/0615/115637327.shtm

代码

码云

https://gitee.com/huangjialin3344/leet-code-test/tree/master/LeetCode_time_1022/src/main/java/com/review/backpack_01

总结

一句话先循环物品再循环体积再循环决策

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

Expect脚本实战：多条件匹配与防卡死技巧

在自动化测试和系统初始化中，我们常常使用 Expect 脚本来完成一系列交互操作，比如自动输入密码、监听输出并作出响应。然而，实际项目中可能遇到多步骤输出匹配的场景：只有在先匹配到某一行输出，再匹配到另一行输出时，才需要做出响应。同时，如果 “testX failed” 出现了，但 “set params error” 没有在合理时间内出现，不要卡死，而是打印警告并继续。这个写法的问题在于：如

2048 AI社区

AI模型版本控制的标签管理：架构师的技巧

在AI模型生命周期中，版本控制是保障模型可追溯性、协作效率与生产可靠性的核心环节。而标签管理作为版本控制的"语义接口"，其设计质量直接决定了团队对模型版本的理解、检索与复用能力。本文从架构师视角出发，结合第一性原理与MLOps实践，系统阐述AI模型标签管理的理论框架、架构设计、实现机制与高级考量。通过拆解标签的"唯一标识+语义描述"本质，提出四维标签模型。