DP --- knapsack problem

knapsack problem

01 knapsack problem （ Choose at most one object ）

​ The so-called state is an unknown . State representation considers how many dimensions to represent the problem .

​ State representation is considered from two aspects , What is the set represented ,f(i,j) Represents what the attributes of the collection are . Each state represents a set , Just find out f() It represents the set , For example, the knapsack problem is the set of all choices . because f(i,j) Is a number , Represents a collection , Number is a certain attribute of this set

Properties generally include max,min, Number . The knapsack problem is the maximum . A bunch of choices represented by sets , A set of all options . The selection method meets two conditions , first ： Only once i Choose from the items . the second ： The total volume of the selected items is less than or equal to J.f() It represents all sets that meet the conditional selection .f() The number saved is the maximum value of the total value of each option in the set .

​ State calculation is how to calculate each state step by step ———— Partition of sets

​ It is to consider dividing the current set into several smaller subsets , So that it can be calculated . Principle of division ： Not heavy （ An element cannot belong to two sets ）（ The maximum value can be repeated ）, No leakage （ A set element does not belong to any set ）.

​

​ Then take the maximum of the two parts .

dp The optimization of the problem is to code , Calculate the equation to make equivalent deformation

01 knapsack problem

public class Main{
    public static void main(String[] args) throws Exception {
        //  Read the code of data 
        Scanner reader = new Scanner(System.in);
        //  The number of items is N
        int N = reader.nextInt();
        //  The capacity of the backpack is V
        int V = reader.nextInt();
        //  A length of N Array of , The first i The first element represents i The volume of items ;
        int[] v = new int[N + 1] ;
        //  A length of N Array of , The first i The first element represents i The value of an item ;
        int[] w = new int[N + 1] ;

        for (int i=1 ; i <= N ; i++){
            //  Next there is  N  That's ok , Each line has two integers :v[i],w[i], Space off , Separate indication control i The volume and value of items 
            v[i] = reader.nextInt();
            w[i] = reader.nextInt();
        }
        reader.close() ;

        //  Official working code 
        /*
         Define a second-order matrix dp[N+1][V+1],
         Here's why N+1 and V+1, It's because 0 The row indicates that only the 0 When it's an item , That is, when there are no objects 
         The first 0 The column indicates that the volume of the backpack is 0 When , That is, when you can't hold anything 

        dp[i][j] It means that   Only the front i Items , The capacity of the backpack is j Under the circumstances , The maximum value of the items in the backpack 
         about dp[i][j] There are two situations ：
        1.  Do not select the current i Item / The first i Items are larger than backpacks , be dp[i][j] = dp[i-1][j]
        2.  Select the current second i Item （ Potential requirements i The volume of each item is less than or equal to the total capacity of the backpack ）, The maximum value of the items that can be loaded is ：
             The value of current goods   add   The remaining capacity of the backpack can only be selected i-1 The maximum value of an item 
            dp[i][j] = dp[i-1][j-v[i]] + w[i]
        dp[i][j] In two cases, choose the larger case as the current optimal solution ;
         namely ：
        if(j >= v[i]):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
        else:
            dp[i][j] = dp[i-1][j]
        */
        int[][] dp = new int[N+1][V+1];
      for(int j = 0; j <= V; j++){
        dp[0][j] = 0;}
        for(int i = 1; i <= N; i++){
            for(int j = 0; j <= V; j++){
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][V]);
    }
}