---

0 - 1 knapsack problem

1. Looking for maximum value

The standard 01 knapsack

What is the maximum value of filling ?

1. The solution to violence is dps Deep backtracking algorithm （ Load the backpack And no backpack ）
2. Non violent use dp The equation is dynamically recursive

1.1 Definition dp Array dp[i][j]

i Indicates the column length , That is, different objects appear
j Indicates the president , But the line at this time , For the possibility of loading different weights , in other words 0 It's also possible not to install , therefore （j = Maximum weight + 1）
And the corresponding dp[i][j] There is value .

1.2 Two dimensional array implementation

import java.util.*;

/** * @author JMWANG */
import java.io.*;

class Good {
    
    // value 
    int value;
    // weight 
    int weight;

    Good(int v, int p) {
    
        this.value = v;
        this.weight = p;
    }

    Good() {
    
    }

    public void setValue(int v) {
    
        this.value = v;
    }

    public void setWeight(int p) {
    
        this.weight = p;
    }
}

public class Main {
    

    public static void main(String[] args) throws IOException {
    
        // Maximum backpack weight 
        int n = 4;
        // Build items 
        List listGood = new ArrayList();
        listGood.add(new Good(15, 1));
        listGood.add(new Good(20, 3));
        listGood.add(new Good(30, 4));
        //dp Recursive equation construction 
        int[][] goods = new int[listGood.size()][n + 1];
// for (int i = 0; i < goods.length; i++) {
    
// System.out.println(Arrays.toString(goods[i]));
// }
        dp(n, goods, listGood);
        System.out.println(goods[listGood.size() - 1][n]);
    }

    public static void dp(int N, int[][] dp, List<Good> listGood) {
    
        // The relationship between the upper and lower levels 
        //dp[i][j] = max(listGood.get(i),)
        for (int i = 0; i < listGood.size(); i++) {
    
            for (int j = 0; j < N + 1; j++) {
    
                // initialization dp equation 
                if (j == 0) {
    
                    dp[i][j] = 0;
                    continue;
                }
                if (i == 0) {
    
                    dp[i][j] = listGood.get(i).weight <= N ? listGood.get(i).value : 0;
                    continue;
                }

                // If at present   weight  j <  The weight of the current item , Just directly transfer the weight of the upper layer down 
                if (j < listGood.get(i).weight) dp[i][j] = dp[i - 1][j];
                    // If at present   weight  j >=  The weight of the current item  , We need to compare 
                    // The value of the vertical layer is greater   still   On the left + The value of the current item is greater 
                else {
    
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - listGood.get(i).weight] + listGood.get(i).value);
                }
                LookDP(dp);
                System.out.println("______________________________");
            }
        }
    }

    public static void LookDP(int[][] goods) {
    
        for (int i = 0; i < goods.length; i++) {
    
            for (int j = 0; j < goods[i].length; j++) {
    
                System.out.print(goods[i][j] + " ");
            }
            System.out.println();
        }
    }
}

1.3 One dimensional array implementation

    public static void testWeightBagProblem(int N, List<Good> listGood){
    
        int len = listGood.size();
        // Definition dp Array ,dp[j] Indicates that the backpack capacity is j when , The greatest value you can get 
        int[] dp = new int[N +1];
        // traversal order ：  Go through the items first , Then traverse the backpack capacity 
        for(int i=0;i<len;i++){
    
            for(int j=N;j>=listGood.get(i).weight;j--){
    
                System.out.println(Arrays.toString(dp));
                dp[j] = Math.max(dp[j], dp[j-listGood.get(i).weight]+listGood.get(i).value);
            }
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(dp[N]);
    }

Please correct me if there is any mistake