Tag dynamic programming - preliminary knowledge for question brushing -2 0-1 knapsack theory foundation and two-dimensional array solution template

The knapsack problem that interview often inspects

Before you look down , It is necessary to pass an article , To familiarize yourself with the process of filling out the backpack question : [ Am I ](https://www.yuque.com/docs/share/2fbdf1a7-1499-4696-ab71-1df56240d2d1?# 《 Dynamic programming - knapsack problem 》)

One , 0-1 knapsack problem

1. determine dp The meaning of arrays and subscripts

dp[i][j], among i Represents objects , j It refers to the capacity of the backpack

Such as dp[i - 1][j] Indicates from number 0~i-1 The items Choose from any of the following , Put in Capacity of j The backpack , The sum of values dp[i -1][j] What is the maximum .

2. Determine the recurrence formula

3. dp How to initialize an array

4. Determine the traversal order

5. Give an example to deduce dp Array

A. Two dimensional array 0-1 Backpack template

[ Code implementation ]

 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;
        // Definition dp Array ：dp[i][j] Indicates that the backpack capacity is j when , front i The maximum value an item can get 
        int[][] dp = new int[wlen + 1][bagsize + 1];
        // initialization ： The capacity of the backpack is 0 when , The value you can get is 0
        for (int i = 0; i <= wlen; i++){
    
            dp[i][0] = value0;
        }
        // traversal order ： Go through the items first , Then traverse the backpack capacity 
        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]);
                }
            }
        }
        // Print dp Array 
        for (int i = 0; i <= wlen; i++){
    
            for (int j = 0; j <= bagsize; j++){
    
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }