How to abstract a problem into a 0-1 knapsack problem in dynamic programming

️ How to abstract the problem into 0-1 knapsack ️

Explain how to abstract the problem into 0-1 knapsack problem .

The weight of the last stone  II

subject ：

1049.  The weight of the last stone  II

There is a pile of stones , Use an array of integers  

stones

  Express . among  

stones[i]

  It means the first one  

i

  The weight of a stone .

Every round , Choose from

Any two stones

, Then smash them together . Suppose the weights of the stones are  

x

  and  

y

, And  

x <= y

. The possible results of crushing are as follows ：

• If  
  x == y
  , Then both stones will be completely crushed ;

• If  
  x != y
  , So the weight is  
  x
    The stone will be completely crushed , And the weight is  
  y
    The new weight of the stone is  
  y-x
  .

Last ,

There's only one piece left at most

  stone . Return to this stone  

The smallest possible weight

 . If there is no stone left , Just go back to  

0

.

Example  1：

Input ：stones = [2,7,4,1,8,1]
Output ：1
explain ：
Combine  2  and  4, obtain  2, So the array turns into  [2,7,1,8,1],
Combine  7  and  8, obtain  1, So the array turns into  [2,1,1,1],
Combine  2  and  1, obtain  1, So the array turns into  [1,1,1],
Combine  1  and  1, obtain  0, So the array turns into  [1], This is the optimal value .


Example  2：

Input ：stones = [31,26,33,21,40]
Output ：5


Tips ：

• 1 <= stones.length <= 30

• 1 <= stones[i] <= 100

Their thinking

analysis ：

The title tells us the weight of each stone , After the two stones are crushed , There will be only stones with positive difference in weight , The stone may be involved in the crushing operation again , The title requires that a pile of stones be crushed in pairs many times , The last piece left  

Minimum

  weight .

Two stones “ When crushing ” The heavier stones can be divided into groups , It's called a pile of , When crushing , It's equivalent to giving a lot of stones

+

The weight , Divide the smaller stones into groups , It's called a small pile , Give a small pile of stones

-

The weight , When we don't consider putting the crushed stone back , In essence, it's computing

+

or

-

The value of the obtained formula .

If you consider crushing the stone and putting it back , In fact, the essence is to reorganize the originally divided stones , For example, if there are two stones weighing

a

, 

b

, Satisfy

a>=b

, The weight of the crushed new stone is

a-b

, We might as well call this newly obtained stone “ Smash the rebirth stone ”, The stone meets a stone larger than its own weight , Weight is

c

, After crushing again , Weight is

c-(a-b)

, We found that compared with the original formula , It's just

a

The weight of is changed to

-

,

b

The weight of is changed to

+

, In other words, the weights of the two stones are exchanged , Empathy ,“ Smash the rebirth stone ” Encounter a stone smaller than its own weight , Weight is

d

, Then the weight after crushing becomes

(a-b)-d

,

a

,

b

The weight of does not change . although

a

,

b

The weight of has changed , That is, a single stone in a large pile is not necessarily heavier than a single stone in a small pile , But the sum of the weight of a large pile will still be greater than the sum of the weight of a small pile . Because the weight of a lot of stones is all

+

, The weight of all the stones in the small pile is

-

, So we might as well call it

+

Weight heap , The small pile is called

-

Weight heap .

Summary analysis , The stone has been crushed many times , The change is only in which group , It's just the boundary condition of the group , From which of the two stones is heavier to the final stone, the weight given is

+

still

-

, So in essence, it is to add... To the elements in the stone pile weight array

+/-

Number , Get a calculation expression , Then find the value of this expression , Meet the closest

0

Not less than

0

The value of the expression is the answer we want , That is, the weight of the last stone .

So at this time , The problem unknowingly turns into ： Give you the weight of a pile of stones , Each stone can only be selected once , You can add the weight of this stone every time , You can also reduce the weight of the stone , Not less than 0 Minimum weight of .

Then it's different from what I did before [ To divide into equal and subsets ] Is that question very similar ？ We are endowed with

+

Weight the stones into a group , To be endowed with

-

Weight the stones into a group , These two groups are equivalent to two subsets of the array , Find the minimum difference between two subsets .

Might as well set

+

The total weight of the weight pile is

big_sum

, Might as well set

-

The total weight of the weight pile is

small_sum

, The difference in weight is

big_sum-small_sum

The absolute value of . Suppose the total weight of the rock pile is

sum

, be

sum=big_sum+small_sum

, After the above analysis

big_sum>=small_sum

.

It's not hard to launch

small_sum<=sum/2

, That is, the problem becomes to select several elements from the stone pile weight array , Not more than

sum/2

The largest element and , This is completely 0-1 It's a knapsack problem .

Finally, take twice the maximum sum and subtract

sum

What you get is the weight of the last stone .

State definition ：

It means before

Of the elements , No more than

The largest element and , Each of these elements can only be selected once .

Determine the initial state ：

Let's consider being

When, it means that there are no elements to choose , So no matter

Why is it worth it ,

.

State transition equation ：

We'll consider choosing the second option

Elements , Weight is

, If we don't select this element ,

, If we choose this element , The premise must meet

, here

, Because it is to find the maximum , So choose the bigger one .

So the final state transition equation is

.

Implementation code ：

class Solution {
 public int lastStoneWeightII(int[] stones) {
 int sum = 0;
 for (int x : stones) {
 sum += x;
 }
 int ret = sum / 2;
 int n = stones.length;
 int[][] dp = new int[n+1][ret+1];
 for (int i = 1; i <= n; i++) {
 for (int j = 0; j <= ret; j++) {
 int x = dp[i-1][j];
 int y = j >= stones[i-1] ? dp[i-1][j-stones[i-1]] + stones[i-1] : 0;
 dp[i][j] = Math.max(x, y);
 }
 }
 return sum - 2 * dp[n][ret];
 }
}


Time complexity ：$O(n

sum/2)

O((n+1)

(sum/2+1))$

Rolling array optimization ：

class Solution {
 public int lastStoneWeightII(int[] stones) {
 int sum = 0;
 for (int x : stones) {
 sum += x;
 }
 int ret = sum / 2;
 int n = stones.length;
 int[][] dp = new int[2][ret+1];

 for (int i = 1; i <= n; i++) {
 for (int j = 0; j <= ret; j++) {
 int index = (i-1) & 1;
 int x = dp[index][j];
 int y = j >= stones[i-1] ? dp[index][j-stones[i-1]] + stones[i-1] : 0;
 dp[i&1][j] = Math.max(x, y);
 }
 }
 return sum - 2 * dp[n&1][ret];
 }
}


Time complexity ：$O(n

sum/2)

O(2

(sum/2+1))$

One dimensional array optimization ：

Rely only on the previous line of

And

, Update No

Column value

The value of the column must still be the value that has not been updated , So take the way of traversal from back to front , In order to ensure

,

The minimum value of is

.

class Solution {
 public int lastStoneWeightII(int[] stones) {
 int sum = 0;
 for (int x : stones) {
 sum += x;
 }
 int ret = sum / 2;
 int n = stones.length;
 int[] dp = new int[ret+1];
 for (int i = 1; i <= n; i++) {
 for (int j = ret; j >= stones[i-1]; j--) {
 int x = stones[i-1];
 dp[j] = Math.max(dp[j], dp[j-x]+x);
 }
 }
 return sum - 2 * dp[ret];
 }
}


Time complexity ：

Spatial complexity ：

practice ： Objectives and

subject ： 

494.  Objectives and

Give you an array of integers  

nums

  And an integer  

target

 .

Add... Before each integer in the array  

'+'

  or  

'-'

 , And then concatenate all the integers , You can construct a  

expression

 ：

• for example ,
  nums = [2, 1]
   , Can be in  
  2
    Before adding  
  '+'
   , stay  
  1
    Before adding  
  '-'
   , And then concatenate them to get the expression  
  "+2-1"
   .

Returns the 、 The result is equal to  

target

  Different  

expression

  Number of .

Example  1：

Input ：nums = [1,1,1,1,1], target = 3
Output ：5
explain ： Altogether  5  Ways to make the ultimate goal and  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
+1 + 1 + 1 + 1 - 1 = 3


Example  2：

Input ：nums = [1], target = 1
Output ：1


Tips ：

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• 0 <= sum(nums[i]) <= 1000

• -1000 <= target <= 1000

Problem solving

analysis ：

The problem is to give arrays

nums

Element addition of

+/-

The weight , So that the value of the formula is

target

, With the above 【 The weight of the last stone  II】 The difference is that the result of the former calculation formula is not less than

0

The minimum value of , Here is the result of finding the formula, which is

target

Number of alternatives , In essence, there are still 0- knapsack problem , It's just that the corresponding relationship between value and object space has changed , That is, the value of each item is

1

.

Let's first consider the limit boundary of the formula , You might as well set up an array

nums

The sum of the absolute values of the elements is

s

, When the weights are all

-

when , The result of the formula is

-s

, When the weights are all

+

when , The result of the formula is

s

, So the range of the formula is

An integer in an interval , altogether

individual .

Then let's consider the definition of state .

State definition ：

Definition

For the former

The value of the formula formed by weighting the elements is

Number of alternatives ,

.

We know that the range of the formula is

An integer in an interval , Because the subscript of the array cannot be negative , Therefore, when we define the dynamic programming array, we need to offset to the right

position , namely

Target value in

, that

The target value in is

, It is not difficult to deduce that the actual subscript value is

. The range of the formula is

It's an integer , Therefore, the number of columns of the dynamic programming array to be applied for is

.

Determine the initial state ：

When no element can be weighted , The result can only be

0

, So only when

j

by

0

There is a scheme , There is no plan in other cases , We consider this as the initial state , be

,

when

.

State transition equation ：

The so-called weighting of array elements

+/-

In fact, it determines whether the element is added or subtracted , Let's consider the second

i

Elements , Suppose the value of this element is

t

, If you choose to add , Then the number of schemes is

, Premise is

, Choose minus if , Then the number of schemes is

, Premise is $j+s+t<=2

s

j+s-t<0

j+s+t>2

s

0$.

The equation of state transfer is

.

Implementation code ：

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 // Dynamic programming
 // State transition equation dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
 //i Represents the front of the array i Elements ,j Indicates goals and ,dp[i][j] It means before i In elements +/- obtain j Number of alternatives
 // Consider the extreme , The sum of the absolute values of the target and the elements whose maximum value is the array is recorded as s, The minimum value is -s, therefore j The possible values of 2s+1 individual

 //1.  Find the sum of the absolute values of array elements
 int s = 0;
 for (int x : nums) {
 s += Math.abs(x);
 }
 // If target The absolute value is greater than the maximum value of the array target sum , There can be no legal scheme
 if (Math.abs(target) > s) {
 return 0;
 }
 //2.  Create dynamic programming array
 int len = nums.length;
 int[][] dp = new int[len + 1][2 *s + 1];

 //3.  initialization ,0->-s,s->0
 dp[0][s] = 1;

 //4.  Deal with the rest
 for (int i = 1; i <= len; i++) {
 int t = nums[i - 1];
 for (int j = -s; j <= s; j++) {
 // In power, it is important to + when , If the legal scope is met , add dp[i - 1][j + s - t]
 if (j + s - t >= 0) {
 dp[i][j + s] += dp[i - 1][j + s - t];
 }
 // In power, it is important to - when , If the legal scope is met , add dp[i - 1][j + s + t]
 if (j + s + t <= 2 * s) {
 dp[i][j + s] += dp[i - 1][j + s + t];
 }
 }
 }
 return dp[len][target+s];
 }
}


Time complexity ：$O(2

len

s)

O(2

len

s)$

Rolling array optimization ：

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 // Dynamic programming
 // State transition equation dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
 //i Represents the front of the array i Elements ,j Indicates goals and ,dp[i][j] It means before i In elements +/- obtain j Number of alternatives
 // Consider the extreme , The sum of the absolute values of the target and the elements whose maximum value is the array is recorded as s, The minimum value is -s, therefore j The possible values of 2s+1 individual

 //1.  Find the sum of the absolute values of array elements
 int s = 0;
 for (int x : nums) {
 s += Math.abs(x);
 }
 // If target The absolute value is greater than the maximum value of the array target sum , There can be no legal scheme
 if (Math.abs(target) > s) {
 return 0;
 }
 //2.  Create dynamic programming array
 int len = nums.length;
 int[][] dp = new int[2][2 *s + 1];

 //3.  initialization ,0->-s,s->0
 dp[0][s] = 1;

 //4.  Deal with the rest
 for (int i = 1; i <= len; i++) {
 int t = nums[i - 1];
 for (int j = -s; j <= s; j++) {
 // When updating values , You need to zero the value of the original line
 dp[i&1][j + s] = 0; 
 // If the value of the left boundary is satisfied , add dp[i - 1][j + s - t]
 if (j + s - t >= 0) {
 dp[i&1][j + s] += dp[(i-1)&1][j + s - t];
 }
 // If the value of the right boundary is satisfied , add dp[i - 1][j + s + t]
 if (j + s + t <= 2 * s) {
 dp[i&1][j + s] += dp[(i-1)&1][j + s + t];
 }
 }
 }
 return dp[len&1][target+s];
 }
}


Time complexity ：$O(2

len

s)

O(4*s)$

Because the data of the current line is updated , It has something to do with the front and back of the previous line , Therefore, it is not suitable for one-dimensional optimization for this problem , But when we define States , Considering

All values in the interval , This includes some state values that cannot be obtained in the target situation . Let's optimize according to this point .

Optimization plan

For example, when the topic is given

Not for

and

when , Then these two values are invalid status values . In order to avoid these invalid state values , Let's start again and analyze , We will give

The weight is divided into a group called 【 Positive weight part 】, On the contrary, it will give

Are divided into a group called 【 Negative weight part 】, You might as well set the sum of the absolute value elements of the array to

,【 Negative weight part 】 The sum of the absolute value elements of is

, be 【 Positive weight part 】 The sum of the elements is

, We can do the following derivation . From the meaning of the title , The target

by 【 Positive weight part 】 The calculated value of minus 【 Negative weight part 】 Calculated value （ The absolute value ）.

According to inference , Just scrape together

, that 【 Positive weight part 】 That's for sure , So the problem becomes to use only

, Scrape out... From the array

Number of alternatives , But the premise is

It can be

to be divisible by , If it can't be

to be divisible by , Can't come up with

, The number of schemes is directly

, So you need to be in

In the case of an even number , There will be an effective scheme .

In the original question

Will be given a negative weight , The remaining elements will be given a positive weight , From the above analysis, we can begin to define the State .

State definition ：

Represents from the front of the array

Of the elements （ Each element can only be selected once ）, The sum of the elements is exactly

Number of alternatives .

Determine the initial state ：

When there are no elements to choose from , Obviously, except

The rest have no plans .

State transition equation ：

For the first

Elements , The value is

, If you don't choose , Then the number of schemes is

, If you choose , Then the number of schemes

, Total number of schemes

.

Implementation code ：

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 // Dynamic programming
 // For the first i Elements , The value is t, If you don't choose , Then the number of schemes dp[i-1][j], If you choose , Then the number of schemes dp[i-1][j-t], Total number of schemes dp[i][j]=dp[i-1][j]+dp[i-1][j-t].

 //1.  Find the sum of the absolute values of array elements
 int s = 0;
 for (int x : nums) {
 s += Math.abs(x);
 }
 int m = (s - target) / 2;
 // If target The absolute value is greater than the maximum value of the array target sum , perhaps s-target Not even numbers , There can be no legal scheme
 if (Math.abs(target) > s || (s - target) % 2 != 0) {
 return 0;
 }
 //2.  Create dynamic programming array , One dimensional optimization
 int len = nums.length;
 int[][] dp = new int[len+1][m+1];

 //3.  initialization dp[0][0] = 1;
 dp[0][0] = 1;

 //4.  Deal with the rest
 for (int i = 1; i <= len; i++) {
 int t = nums[i - 1];
 for (int j = 0; j <= m; j++) {
 dp[i][j] = dp[i-1][j];
 if (j >= t) {
 dp[i][j] += dp[i-1][j-t];
 }
 }
 }
 return dp[len][m];
 }
}


Time complexity ：

Spatial complexity ：

Rolling array optimization ：

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 // Dynamic programming
 // For the first i Elements , The value is t, If you don't choose , Then the number of schemes dp[i-1][j], If you choose , Then the number of schemes dp[i-1][j-t], Total number of schemes dp[i][j]=dp[i-1][j]+dp[i-1][j-t].

 //1.  Find the sum of the absolute values of array elements
 int s = 0;
 for (int x : nums) {
 s += Math.abs(x);
 }
 int m = (s - target) / 2;
 // If target The absolute value is greater than the maximum value of the array target sum , perhaps s-target Not even numbers , There can be no legal scheme
 if (Math.abs(target) > s || (s - target) % 2 != 0) {
 return 0;
 }
 //2.  Create dynamic programming array , One dimensional optimization
 int len = nums.length;
 int[][] dp = new int[2][m+1];

 //3.  initialization dp[0][0] = 1;
 dp[0][0] = 1;

 //4.  Deal with the rest
 for (int i = 1; i <= len; i++) {
 int t = nums[i - 1];
 for (int j = 0; j <= m; j++) {
 dp[i&1][j] = dp[(i-1)&1][j];
 if (j >= t) {
 dp[i&1][j] += dp[(i-1)&1][j-t];
 }
 }
 }
 return dp[len&1][m];
 }
}


Time complexity ：

Spatial complexity ：

One dimensional array optimization ：

According to the state transition equation, we can find that

Only with the previous line

And

of , therefore

Updating is better than

before , And

, Therefore, one-dimensional optimization needs to traverse from back to front ,

The minimum value is

, Guarantee

.

class Solution {
 public int findTargetSumWays(int[] nums, int target) {
 // Dynamic programming
 // For the first i Elements , The value is t, If you don't choose , Then the number of schemes dp[i-1][j], If you choose , Then the number of schemes dp[i-1][j-t], Total number of schemes dp[i][j]=dp[i-1][j]+dp[i-1][j-t].

 //1.  Find the sum of the absolute values of array elements
 int s = 0;
 for (int x : nums) {
 s += Math.abs(x);
 }
 int m = (s - target) / 2;
 // If target The absolute value is greater than the maximum value of the array target sum , perhaps s-target Not even numbers , There can be no legal scheme
 if (Math.abs(target) > s || (s - target) % 2 != 0) {
 return 0;
 }
 //2.  Create dynamic programming array , One dimensional optimization
 int len = nums.length;
 int[] dp = new int[m+1];

 //3.  initialization dp[0] = 1;
 dp[0] = 1;

 //4.  Deal with the rest
 for (int i = 1; i <= len; i++) {
 int t = nums[i - 1];
 for (int j = m; j >= t; j--) {
 dp[j] += dp[j-t];
 }
 }
 return dp[m];
 }
}


Time complexity ：

Spatial complexity ：

Reference material ：

Miyoshi trefoil backpack problem