Knapsack problem of dynamic programming

In dynamic programming, the right class of problems is derived from the knapsack problem. Its core is to give an array nums[i] and select some data from nums[i] according to some requirements to meet some requirements

More subdivision is whether the elements in a pile of sets can be taken repeatedly. Then someone on the Internet raised the question of 01 knapsack and complete knapsack

For example, common

  • Select elements from the array. Each element has weight and value. Select elements from the array so that their weight is within a certain range and their value is the largest
  • Select the elements from the array so that the least elements are selected so that their sum is target
  • Select the element from the array and find the possibility that the selected element is target
  • Pick the elements from the array so that the sum is half the sum of all the elements in the array

These problems can be applied to a class of dynamic programming

  • The value of [j] can be simplified to the value of [j] in the previous state, which can be determined
  • The state transition equation is generally based on whether the i-th element of the traversal is selected. If it is selected, there will be some result. If it is not selected, there will be some result. From it, select a situation that meets the meaning of the question or the sum of the two. In short, the previous state migration process
  • It is often necessary to infer the initial state based on the meaning of the question, such as dp[i][0] or dp[0][j]
  • You can define boolean [] [] or int [] [] arrays

Knapsack problem ideas

state

array

Select to perform status migration

The first step is to clarify the status:

  • The first step is to clarify two points: [status] and selection]. First, talk about the status. How can we describe a problem situation? Given several optional items and the limit of the capacity of a backpack, a backpack problem is formed, right? So there are two states, namely [Backpack Capacity] and [optional items]
    *Besides, choice is also easy to think of. For each item, what can you choose? Is the choice [pack in backpack] or [not pack in backpack] (corresponding to whether the element in the array is selected or not), if it is not selected, we will directly consider the previously selected problem. If it is selected, 'we also need to consider whether we can select repeatedly, which can be further divided into 01 backpack problem and complete backpack problem

    The second part defines the dp array:

    • What is dp array? In fact, it is an array describing the situation of the problem. In other words, we just made it clear what [state] the problem has. Now we need to express the state with dp array
    • Generally, a two-dimensional array can be used for state compression. For example, the current state dp[i] is only related to the previous state dp[i-1] or the previous state dp[i-2], so there is no need to use the state array to save so many states
    • The definition of dp[i][w] is as follows: for the money I items in the collection, when the capacity of the backpack is w, the maximum value that can be loaded in this case is dp[i][w]

Part III: thinking about the logic of state transition

Simply put, it is the effect of selecting or not selecting the ith element of the array
dp[i][w] the maximum price of the first I items in W's backpack

  • If the ith item is not selected, dp[i-1][w]
  • The ith item selection dp[i-1][w-weight[i-1]]+val[i-1]

Part IV: thinking about baseCase

baseCase is often dp[i][0] or dp[0][i]

Step 5: integrate code:

In this step, you often need to make various choices for the states defined above, and finally return to dp[n] []

int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0

for i in [1..N]:
    for w in [1..W]:
        dp[i][w] = max(
            Put the item i Put it in your backpack,  
            Don't put things i Put it in your backpack
        )
return dp[N][W]

After choosing the item i in the backpack, think about whether the elements in the array can be valued repeatedly; It is further derived into complete knapsack problem and 01 knapsack problem

01 knapsack problem basic version

01 knapsack problem

  • Define States i and w as the first i elements of the item and the weight of the backpack as w
  • Define the maximum price of the first i elements of the array dp[i[w] into the backpack with the weight of W
  • Selection is a question of selecting or not selecting I items. dp[i][w]= dp[i-1][w]+dp[i-1][w-weight[i-1]]+val[i-1]
  • Initial state DP [0] [w] = 0 DP [i] [0] = 0
  • The following is to install it into the framework for traversal
package com.zj.FDynamicProgramming.taolu;

/**
 * @Author Zhou Jian
 * @Date 2020/8/8
 */
public class PackageBase01 {

    /**
     * The first step is to clarify two points, "state" and "choice". Therefore, there are two states, namely "Backpack Capacity" and "optional items".
     *First, let's look at the "states" just found. There are two, that is, we need a two-dimensional dp array. One dimension represents optional items and one dimension represents the capacity of the backpack.
     * dp[i][w]The definition of is as follows: for the first I items, the capacity of the current backpack is w. in this case, the maximum value that can be loaded is dp[i][w].
     * For example, if dp[3][5] = 6, it means that for a given series of items, if only the first three items are selected, when the backpack capacity is 5, the maximum value that can be loaded is 6.

        dp[i][w]=max( dp[i-1][w],dp[i-1][w-wt[i]]+val[i])
             for i in [1..N]:
                 for w in [1..W]:
                     dp[i][w] = max(
                         Put the items i into the backpack,
                         Don't pack items i into your backpack
                     )
                 return dp[N][W]
     */


        public  int knaspack(int[] w,int[] val,int weight){

            if(weight==0) return 0;
            // dp[i][j] the maximum value of j in the first I items
            int[][] dp = new int[w.length+1][weight+1];
            // In the first i items
            for(int i=1;i<w.length+1;i++){
                //The maximum value that can be obtained by loading the backpack with the capacity of j
                for(int j=1;j<weight+1;j++){
                    if(j-w[i-1]>=0) {
                        // The maximum value that can be obtained by loading a backpack with a capacity of j in the first i items
                        // dp[i-1][j] the i-th item is not loaded
                        // The i-th item is packed in DP [i-1] [J-W [i-1]) + Val [i-1] 01 backpack. At this time, you can only take it from the first i-1 item
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + val[i - 1]);
                    }
                }
            }

            return dp[w.length][weight];

        }

    public static void main(String[] args) {
        int[] wt = {2,1,3};
        int[] val = {4,2,3};
        PackageBase01 packageBase01 = new PackageBase01();
        int knaspack = packageBase01.knaspack(wt, val, 4);
        System.out.println(knaspack);
    }





}

LeetCode416 segmentation and subsets

For the 01 knapsack problem in disguise, find out whether there is a subset in the array, and the value is sum/2

  • Define i as the value of the first i elements in the array rounded up by j
  • Whether the first I elements in dp[i][j] array can be aggregated into j elements (true or false)
  • Whether to select the ith element dp[i][j]= dp[i-1][j]|dp[i-1][j-vals[i]]
  • baseCase dp[i][0] = true
  • Sleeve into frame
package com.zj.FDynamicProgramming.taolu;

/**
 * @Author Zhou Jian
 * @Date 2020/8/8
 * Segmentation and subset problem
 */
public class Problem416 {

    /**
     * Whether and from the array are sum/2
            dp[i][w]  Select whether the sum of the values from the previous i elements is w
            dp[i][w] = dp[i-1][w] | dp[i-1][w-val[i]]
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {

        if(nums==null) return false;
        int sum = 0;
        for(int i=0;i<nums.length;i++) sum=sum+nums[i];
        if(sum%2!=0) return false;
        sum = sum/2;
        boolean[][] dp = new boolean[nums.length+1][sum+1];
        // dp[][0] = true
        for(int i =0;i<nums.length+1;i++) dp[i][0] = true;

        for(int i=1;i<nums.length+1;i++){
            for(int j=1;j<sum+1;j++){
                if (j-nums[i-1] >= 0) {
                    // Whether to select the i th element
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]];
                }
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[nums.length][sum];
    }



}



LeetCode322 coin rounding (pick the smallest element from the array to make a number)

  • Define the state i j. select coins from i coins to form j
  • Define the minimum number of coins needed by the array dp[i][j] to select elements from the previous I coins to make j
  • You can choose or not choose dp[i][j]= min(dp[i-1][j],dp[i][j-coins[i]]+1) for I coins. Note that this is a complete knapsack problem, and the elements in the array can be selected repeatedly. dp[i][j-coins[i]]+1 is reflected here
  • Define basecase. DP [0] [j] is defined as amount+1 if the number of pages is impossible
  • Just insert it into the frame
  /**
     * dp[i][j] The first i items are rounded up into j the least number, which can be repeated
     * @param coins
     * @param amount
     * @return
     * dp[i][j] Items can be taken repeatedly
     * If the i-th item is not taken, dp[i-1][j]
     *        For the i-th item, there is dp[i][j-coins[i]]. Note that I still starts here
     *        J-coins [i] > 0
     *        Otherwise, only dp[i-1][j] can be taken
     *        dp[i][j] = min(dp[i-1][j],dp[i][j-coins[i-1]]+1) Xu coins-1
     *
     */
    public int coinChange1(int[] coins, int amount){

        if(amount==0) return 0;
        int[][] dp = new int[coins.length+1][amount+1];
        for(int i=0;i<amount+1;i++) {
                dp[0][i] = amount + 1;  //It is impossible to use the first 0 currencies to make up i
        }

        for(int i=0;i<coins.length+1;i++) dp[i][0] = 0;

        for(int i=1;i<coins.length+1;i++){
            for(int j=1;j<amount+1;j++)
                dp[i][j] = amount+1;
        }


        /**
         *dp[i][j]The minimum number of currencies required for the first i currencies to make up j yuan
         *      dp[0][j]
         */
        for(int i=1;i<coins.length+1;i++){
            for(int j=1;j<amount+1;j++){
                if(j-coins[i-1]>=0) {
                    // dp[i-1][j] the ith currency is not selected
                    // dp[i][j-coins[i-1]]+1 the ith currency selection
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]]+1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }

        }
        return dp[coins.length][amount]<amount+1?dp[coins.length][amount]:-1;
    }


LeetCode518 possible number of a number from the array

link

  • Define States i and w. select elements from the first i elements of the array to form w
  • dp[i][w] select the possible number of elements from the first I elements of the array to form W
  • For the ith element, you can select or uncheck (dp[i][w] = dp[i-1][w]+dp[i][w-weight[i-1]])
  • Definition basecase DP [0] [i] = 0, DP [i] [0] = 1
  • Put it into the frame for calculation
 /**
     * Given coins of different denominations and a total amount, write a function to calculate the number of coin combinations that can be added up to the total amount, assuming that there are infinite coins of no denomination.
     *
     * dp[i][j] Possibility of rounding up the first i currencies into j yuan
     *  dp[i-1][j] The possibility that the i-th job does not choose to make up j
     *  dp[i][j-coins[i-1]] The ith choice
     * dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
     *
     * dp[0][j] = 0
     * dp[i][0] = 1
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change3(int amount, int[] coins) {

        if(amount==0) return 1;
        int[][] dp = new int[coins.length+1][amount+1];
        // Initialization of state
        for(int i=0;i<coins.length+1;i++) dp[i][0] = 1;

        // Iteration update status
        for(int i=1;i<coins.length;i++){
            for(int j=1;j<amount+1;j++){
                    // Possible tree of j yuan from the first i currencies
                if(j-coins[i-1]>=0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.length][amount];
    }

Tags: leetcode

Posted by corrupshun on Tue, 24 May 2022 08:27:05 +0300