Dynamic programming (an extension of the 01 knapsack problem)

01 Backpack problem

This has been covered before, so check out theDynamic Programming 01 Backpack Problem
This time, we will focus on some of the issues that expand out under the 01 backpack problem.

Topic I. Partitioning equal and subset

Title Link:leetcode416. split equal and subset
Given a non-empty array containing only positive integers. Is it possible to split this array into two subsets such that the sum of the elements of the two subsets is equal.

take note of:
Each array will contain no more than100
The size of the array will not exceed200

Example 1.

importation: [1, 5, 11, 5]

exports: true

account for: Arrays can be split into[1, 5, 5] cap (a poem)[11].

Example 2.

importation: [1, 2, 3, 5]

exports: false

account for: Arrays cannot be partitioned into two elements and equal subsets.

At first glance, this kind of question feels like a no-brainer, but it's not.
reasoning
1. First think about the fact that since they are to be divided into two equal parts, their sum must be even, otherwise they must not be divided into two equal parts.
2. How can this problem be converted to a 01 backpack problem? It's actually quite simple, first determine what is the capacity of the backpack, what is the capacity of the item, and what is the value of the item.
We can find the sum of all the numbers in the array, so half of it can be figured out after eliminating the fact that it's even, i.e., if I can get half of the sum using these numbers in the array, then that means there must be a way for me to divide it into two equal parts.
Assuming that the sum of all the numbers in the array is even and noted as sum, then half of it is noted as half_sum, which is then the capacity of the backpack. And the entire array is both the weight and the value of the item.
Then the question can be interpreted as what is the maximum value of the item I can fit in with a capacity of half_sum again.
Once this optimal solution is found, it is only necessary to compare it with half_sum for equality.
recurrence formula
Create an array of dp, with i denoting the number of items, j denoting the current capacity, and dp[j] denoting the maximum sum at capacity j.
Initialized to 0 because as long as the current sum is 0, then I can always get a sum greater than 0.
dp[j] = max(dp[j]，dp[j - nums[i]] + nums[i])

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        //Summation
        for(int i = 0;i<nums.size();i++)
        {
          sum+=nums[i];
        }
        // Determine if the number is odd
        if(sum % 2 == 1)  return false;
        //Acquire half of the sum, which is also the capacity of the backpack
        int half_sum = sum/2;
        vector<int> dp(half_sum + 1,0);
        for(int i = 0;i<nums.size();i++)
        {
          for(int j = half_sum;j>=nums[i];j--)
          {
            dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
          }
        }
        return dp[half_sum] == half_sum;
    }
};

Topic II. The Weight of the Last Stone II

Title Link:The Weight of the Last Stone II
There is a pile of rocks, each of which weighs a positive integer.

In each round, any two stones are chosen from among them and crushed together. Assume that the weights of the stones are x and y, and x <= y. Then the possible outcomes of crushing are as follows:

If x== y, then both stones will be completely crushed;
If x!= y, then the stone of weight x will be completely pulverized, and the stone of weight y will have a new weight of y-x.
In the end, there will be at most one stone left. Returns the smallest possible weight of this stone. If there are no stones left, return0。

Example:

Input:[2,7,4,1,8,1]
Output:1
Explanation:
Combination2 cap (a poem)4get2, so the array is transformed into[2,7,1,8,1]Combination
combinatorial7 cap (a poem)8get1, so the array is transformed into[2,1,1,1]Combination
combinatorial2 cap (a poem)1get1, so the array is transformed into[1,1,1]Combination
combinatorial1 cap (a poem)1get0, so the array is transformed into[1], which is the optimal value.

Tip:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

reasoning
1. also want to use the idea of 01 backpack problem to solve this problem, then you have to be clear about the backpack capacity, the weight of the item and the value of the item, I want to get the smallest weight of the stone, then I just need to divide this pile of stones into the weight of the closest to the two can be, so that crushed down, you can certainly get the smallest weight of the stone.

2. After analyzing the nature of the problem, it is close to 01 backpack, the first to determine the maximum capacity of the backpack, the same, we will add up the total mass of all the stones, divided by two is the capacity of the backpack, note that there is no need to determine whether it is an odd number here, because only need to be divided into a pile of this pile of stones in the weight of the closest to the two piles, which may be equal, or may not be equal.

3. Similarly, the weight of a stone represents both its weight and its value.

recurrence formula
Create an array of dp, with i denoting the number of items, j denoting the current capacity, and dp[j] denoting the maximum sum at capacity j.
Initialized to 0 because as long as the current maximum mass sum and sum is 0, then I can always get a mass sum greater than 0.
dp[j] = max(dp[j]，stonesdp[j - [i]] + stones[i])

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0,half_sum = 0;;
        for(int i = 0;i<stones.size();i++)
        {
          sum+=stones[i];
        }
        half_sum = sum/2;
        vector<int> dp(half_sum + 1,0);
        for(int i = 0;i<stones.size();i++)
        {
          for(int j = half_sum;j>=stones[i];j--)
          {
            dp[j] = max(dp[j],dp[j - stones[i]] + stones[i]);
          }
        }
        // Because half_sum is sum/2 rounded down, sum - dp[half_sum] must be greater than or equal to dp[half_sum]'s
        return sum - 2*dp[half_sum];
    }
};

Topic III. Objectives and

Title Link:objectives and

Given an array of nonnegative integers, a1, a2, ..., an, and a target number, S. Now you have two symbols+ cap (a poem)-. For any integer in the array, you can start with the+ maybe-Choose one of the symbols to add in front of it.

Returns the number of ways to make the final array and add symbols to all of the target number S.

Example:

Input: nums: [1, 1, 1, 1, 1], S: 3
Output:5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are5A way to make the final goal and for3。

Tip:

The array is non-empty and will not exceed the length of the20 .
The sum of the initial array will not exceed1000 .
It is guaranteed that the final result returned will be32 The bit integer is stored.

This question was a question in my interview with Tencent, I didn't do it at the time, and I came down to think about it myself in conjunction with the big brother's thoughts, and summarized it.
The first thing that comes to mind is the backtracking method to solve the problem, but if the length of the array is particularly long, then it is easy to exceed the time complexity. The essence of this question to see out, in fact, is still a 01 backpack problem.
reasoning
First of all, define the sum of these numbers as sum, to get the target number S, then there must be two numbers split from sum recorded as all additions+The number of the first and the left_sum, all added-The number gets summed to right_sum, then there is:
left_sum - right_sum = S
And left_sum + right_sum = sum
Then it follows that: left_sum = (sum + S)/2
One thing to note here: left_sum , right_sum , sum, S are all deterministic, so (sum + S)/2 can't be allowed to round down, i.e. sum + S must be even, otherwise there is no way to get the target number
Since sum is fixed, and S is fixed, then it converts to finding the sum of the arrays that get left_sum.
Define dp array, i denotes the subscript of the current number, j denotes the current capacity, and dp[j] denotes the number of all methods that can get the number sum to j.
Then we have: dp[j] += dp[j - nums[i]]
For example, assuming that nums[i] = 2, I now want to ask for the total number of methods that sum to 5 in the current case, so in addition to the total number of methods that I know I can get to 5, I need the total number of methods up to dp[5 - 2] because I know the number of methods in dp[3], so the number of methods in dp[3] is the number of methods in dp[5], so it's just a matter of adding to dp[5].

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int i = 0;i<nums.size();i++)
        {
            sum+=nums[i];
        }
        //Judgment conditions
        if(sum < S || (sum + S) % 2 == 1)   return 0;
        int left_sum = (S + sum) / 2;
        vector<int> dp(size + 1,0);
        dp[0] = 1;
        for(int i = 0;i<nums.size();i++)
        {
            for(int j = left_sum;j>=nums[i];j--)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left_sum];
    }
};