tag动态规划-刷题预备知识-2. 0-1背包理论基础和二维数组解法模板

面试常考察的背包问题

在看下面之前, 有必要通过一篇文章, 来熟悉背包问题填表过程: [点我](https://www.yuque.com/docs/share/2fbdf1a7-1499-4696-ab71-1df56240d2d1?# 《动态规划-背包问题》)

一, 0-1背包问题

1. 确定dp数组以及下标的含义

dp[i][j], 其中i代表的是物品, j指代的是背包的容量

如dp[i - 1][j] 表示从编号为0~i-1的物品 中任意选择, 放入到容量为j的背包, 价值总和dp[i -1][j] 最大为多少。

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

A. 二维数组的0-1背包模板

[代码实现]

 public static void main(String[] args) {
    
        int[] weight = {
    1, 3, 4};
        int[] value = {
    15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
    
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
    
            for (int j = 1; j <= bagsize; j++){
    
                if (j < weight[i - 1]){
    
                    dp[i][j] = dp[i - 1][j];
                }else{
    
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
    
            for (int j = 0; j <= bagsize; j++){
    
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }