Dynamic programming-01 knapsack problem

------ Use  java To write , Logically, all languages are common

One 、 What is? 01 knapsack

（1） Concept

         01 The knapsack problem is M Take out several items and put them in the space for W In my backpack , The weight of each item is wight1 , wight2 to wightn , The corresponding value is money1 , money2 to moneyn ;

         01 The constraint of knapsack is to give several items , There is only one item of each kind , Judge the value of items that can be put into the backpack to the maximum extent that it can bear ;

 

Two 、 How to understand the knapsack problem

（1） Example ：

        There is one 1 kg Value is 15 Yuan's apple 、 One 3 kg Value is 20 Cantaloupe of Yuan 、 One 4kg Value is 30 Durian of Yuan , Use a bearing capacity of 4 kg The backpack , Ask how much fruit the backpack can hold with a maximum value of ？

（2） List comprehension

2.1

        According to the example , Assume the following table , Namely ownership 0 - 3 Kind of fruit 、0 - 4 kg Heavy 5 When a backpack , Ask the maximum value of fruit in it ;

        ( Join in Do not load fruit and 0 kg The situation is to align the number of fruits and the weight of the backpack with the coordinates , Don't join )

	0kg	1kg	2kg	3kg	4kg
Do not load ：0kg          0 element
Apple ：1kg        15 element
Hami melon ：3kg        20 element
durian ：4kg        30 element

 2.2

        Whether it's 0 kg The ultimate value of the backpack without fruit is 0 element , Therefore, these two cases are directly filled as 0 element ;

	0kg	1kg	2kg	3kg	4kg
Do not load ：0kg          0 element	0 element	0 element	0 element	0 element	0 element
Apple ：1kg        15 element	0 element
Hami melon ：3kg        20 element	0 element
durian ：4kg        30 element	0 element

2.3

         When there is only one apple ,1 - 4 kg How much fruit can you put in your backpack ;

        Because there is only one apple , and 1 kg Apple of 1 - 4 kg Can be put into , So when there is only one apple 1 - 4 kg My backpacks are 15 element ;

	0kg	1kg	2kg	3kg	4kg
Do not load ：0kg          0 element	0 element	0 element	0 element	0 element	0 element
Apple ：1kg        15 element	0 element	15 element	15 element	15 element	15 element
Hami melon ：3kg        20 element	0 element
durian ：4kg        30 element	0 element

2.4

        Calculate when you have apple and cantaloupe ,1 - 4 kg How much fruit can you put in your backpack ;

        Because Hami melon is 3 kg so 1 kg and 2 kg Only apples can be put into the heavy backpack , Therefore, the value obtained when there is only apple in the previous line is introduced ;

        When the conditions for putting Hami melon are met , There may be two situations for the value of fruit that can be put ：

        1. Without Hami melon, it is the maximum value of fruit that can be put under the current weight ;

        2. Put in a Hami melon , Then calculate the remaining space , Plus the maximum value that the remaining weight can fit without Hami melon ;（ Because a Hami melon has been put in , There is no second cantaloupe ）

        find 1 、2 Among them, the greater fruit value , It is the maximum value that the current backpack can contain fruit ;

        Therefore, this formula is derived ：（ Max() It means taking a larger value ）

        Max( The value of the fruit stored in the previous row of the current weight , The current value of fruit + The fruit value of the remaining space in the previous line  )

	0kg	1kg	2kg	3kg	4kg
Do not load ：0kg          0 element	0 element	0 element	0 element	0 element	0 element
Apple ：1kg        15 element	0 element	15 element	15 element	15 element	15 element
Hami melon ：3kg        20 element	0 element	15 element	15 element	20 element	35 element
durian ：4kg        30 element	0 element

2.5

        Use the deduced formula to fill in the table with durian ;

	0kg	1kg	2kg	3kg	4kg
Do not load ：0kg          0 element	0 element	0 element	0 element	0 element	0 element
Apple ：1kg        15 element	0 element	15 element	15 element	15 element	15 element
Hami melon ：3kg        20 element	0 element	15 element	15 element	20 element	35 element
durian ：4kg        30 element	0 element	15 element	15 element	20 element	35 element

（2） Code demonstration

2.1

        Create three arrays according to the above method , A storage fruit weight , The value of a stored fruit , A maximum value of the fruit in the backpack in each case , Don't miss the situation when the fruit is not loaded ;

        Weight and value can be directly filled in according to the table , A binary array bag Take the number of fruits in the row , Then take the length of any array directly , Because the weight of the backpack is 4 kg , Therefore, the total number of columns should be 0 - 4 total 5 A place ;

 2.2

         Because when the weight is less than or equal to the storage capacity of the backpack, the formula is  Max( The value of the fruit stored in the previous row of the current weight , The current value of fruit + The fruit value of the remaining space in the previous line  ) , Therefore, several currently defined arrays are substituted into this formula to get ：

                                      

        bag[i][j] = Math.max( bag[i-1][j] , money[i] + bag[i-1][j-wight[i]] );

         Use the formula to traverse the entire array ;

 

 2.3 

        Finally, the answer to the question is obtained by outputting the lower right element of the array ;

 

3、 ... and 、 Code sharing

public class DP_01Bag {
    public static void main(String[] args) {
        int[] wight = { 0 , 1 , 3 , 4 };
        int[] money = { 0 , 15 , 20 , 35 };
        int[][] bag = new int[wight.length][5];


        for (int i = 1; i < bag.length; i++) {
            for (int j = 1; j < bag[i].length; j++) {
                if ( wight[i] > j)
                    bag[i][j] = bag[i-1][j];
                else bag[i][j] = Math.max( bag[i-1][j] , money[i] + bag[i-1][j-wight[i]] );
            }
        }
        System.out.println( bag[bag.length-1][bag[0].length-1] );
    }
}