当前位置：网站首页>0-1 knapsack problem of dynamic programming (detailed explanation + analysis + original code)

0-1 knapsack problem of dynamic programming (detailed explanation + analysis + original code)

2022-06-11 22:27:00 【InfoQ】

knapsack problem ：

It generally refers to a kind of 「 Given value and cost 」, meanwhile 「 Limit decision rules 」, Under such conditions , How to realize the problem of value maximization .

0-1 knapsack ：

「01 knapsack 」 It refers to the value and volume of a given object （ Corresponding 「 Given value and cost 」）, At the specified capacity （ Corresponding 「 Limit decision rules 」） How to maximize the total value of the selected items .

（ From Miyazawa Sanye ）

️0-1 knapsack problem ️

Topic details

Yes N Items and a capacity are V The backpack . Each item has and only has one .

The first i The volume of the item is v[i] , The value is w[i] .

Find out which items to pack in your backpack , The total volume of these items can not exceed the capacity of the backpack , And the total value is the greatest .

Example 1：

 Input : N = 3, V = 4, v = [4,2,3], w = [4,2,3]
 Output : 4
 explain :  Select only the first item , Can maximize value .

Example 2：

 Input : N = 3, V = 5, v = [4,2,3], w = [4,2,3]
 Output : 5
 explain :  Not the first item , Select the second and third item , Can maximize value .

Their thinking

analysis ：

The meaning of this question is to give you a pile of items , There is only one item of each kind , Then select some of these items and put them into the backpack , Without exceeding the capacity of the backpack , Find the maximum total value of the items in the backpack .

simple 0-1 Knapsack general solution

State definition ：

It's essentially from

i

Choose a certain number of items in a certain number of items under the premise of certain space constraints , Find the maximum total value of these items , We can define a two-dimensional array

dp[i][j]

, The value of this array represents the past

i

Select items , At no more than capacity

j

The maximum total value of the goods .（ notes ： Here's the second

i

Item corresponds to array subscript

i

）

Determine the initial state ：

When there is only one item , If the volume of the article

v

No more than backpack capacity

j

, Then the initial value

dp[0][j]=v

, otherwise

dp[0][j]=0

State transition equation ：

For the first

i

Item , Let its capacity be

v[i]

, Value is

w[i]

, We can choose this item or not , If you do not select this item, then

, If you choose this item, there are two situations ：

There is not enough space left in the backpack , Then the item cannot be selected at this time ,

.

There is enough space left in the backpack , Then the total value of the goods at this time is

.

Sum up , The transfer equation is

Implementation code ：

 /**
 *
 * @param N  Number of items 
 * @param C  Backpack Capacity 
 * @param v  The volume of each piece 
 * @param w  The value of everything 
 * @return  The greatest value 
 */
 public int zoKnapsack(int N, int C, int[] v, int[] w) {
 //0-1 The backpack is simple 
 int[][] dp = new int[N][C+1];
 // initialization 
 for (int j = 0; j <= C; j++) {
 dp[0][j] = j >= v[0] ? w[0] : 0;
 }

 // Process the remaining elements 
 for (int i = 1; i < N; i++) {
 for (int j = 0; j <= C; j++) {
 // No election 
 int x = dp[i-1][j];
 // choose 
 int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0;
 // Take the maximum of the two 
 dp[i][j] = Math.max(x, y);
 }
 }
 return dp[N-1][C];
 }

Optimization plan

Rolling array optimization ：

According to the state transition equation

It's not hard to find out , Calculation

A line

The value of is only associated with

The previous line

of , So suppose the total number of items is

n

, The total space of the backpack is

c

, It was necessary to use

n

That's ok

c

Array of columns , It can be optimized to

2

That's ok

c

Two dimensional array of columns , These two lines are used alternately in even and odd order .

among , When performing parity row conversion , have access to

i%2

perhaps

i&1

Subscript substitution , because

&

Operator ratio

%

The operator is stable , So I recommend

i&1

Implementation code ：

 public int zoKnapsackPlus(int N, int C, int[] v, int[] w) {
 //0-1 Knapsack rolling array optimization 
 int[][] dp = new int[2][C+1];
 // initialization 
 for (int j = 0; j <= C; j++) {
 dp[0][j] = j >= v[0] ? w[0] : 0;
 }

 // Process the remaining elements 
 for (int i = 1; i < N; i++) {
 for (int j = 0; j <= C; j++) {
 // No election 
 int x = dp[(i-1) & 1][j];
 // choose 
 int y = j >= v[i] ? dp[(i-1) & 1][j-v[i]] + w[i] : 0;
 // Take the maximum of the two 
 dp[i&1][j] = Math.max(x, y);
 }
 }
 return dp[(N-1) & 1][C];
 }

One dimensional array optimization ：

Let's take another look at the state transition equation ：

, We found that Qiudi

i

Xing di

j

When the value of the column grid , Only with

i-1

The grid of rows is related to , And explicitly rely on the third party

j

Column and the first

j-v[i]

Column , It's equivalent to the new second

j

The column data is only related to the old

j

Column and the old

j-v[i]

Column , So we can optimize the two-dimensional array , Can be optimized into a one-dimensional array , That is, only

Backpack Capacity

dimension .

The maximum value of the optimized item is

dp[j]

, new

dp[j]

With the old

dp[j]

With the old

dp[j-v[i]]

of , That is, calculate a new round

dp[j]

when ,

dp[j-v[i]]

Must be a value that has not been updated , It can be seen from the figure above

dp[j-v[i]]

The position of is

dp[j]

The front of the position , So when updating the maximum total value of a new round , Need to update first

dp[j]

Update the value of

dp[j-v[i]]

Value , therefore

j

The traversal order is from back to front , At the same time, to ensure that

j>=v[i]

, The minimum value of traversal is

v[i]

Implementation code ：

 public int zoKnapsackOnePlus(int N, int C, int[] v, int[] w) {
 //0-1 Knapsack rolling array optimization 
 int[] dp = new int[C+1];
 // initialization 
 for (int j = 0; j <= C; j++) {
 dp[j] = j >= v[0] ? w[0] : 0;
 }

 // Process the remaining elements 
 for (int i = 1; i < N; i++) {
 for (int j = C; j >= v[i]; j--) {
 // No election 
 int x = dp[j];
 // choose 
 int y = dp[j-v[i]] + w[i];
 // Take the maximum of the two 
 dp[j] = Math.max(x, y);
 }
 }
 return dp[C];
 }

practice ： To divide into equal and subsets

subject ：

416. To divide into equal and subsets

To give you one

Contains only positive integers

Non empty

Array

nums

. Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Example 1：

 Input ：nums = [1,5,11,5]
 Output ：true
 explain ： Arrays can be divided into  [1, 5, 5]  and  [11] .

Example 2：

 Input ：nums = [1,2,3,5]
 Output ：false
 explain ： An array cannot be divided into two elements and equal subsets .

Tips ：

1 <= nums.length <= 200

1 <= nums[i] <= 100

Problem solving

analysis ：

The meaning of this question is to give you an array containing only positive integers

nums

, Divide this array into two subsets , And the sum of the elements of the two subsets is equal , That means that the sum of the elements of the two subsets is equal to the original array

nums

Half of the elements and , Now let's remember the original array

nums

The sum of the elements is

sum

, So if

sum

It's odd , How to split the array can not be divided into two elements and equal subsets , Go straight back to

false

that will do , If

sum

For the even , It is possible to separate two elements and equal subsets , Think about it in another way , If one of the subsets can come up with

sum/2

, That other subset can naturally come up with

sum/2

, So at this time, the problem is transformed into ：

Select elements from the array , Each element can only be selected once , Determine whether the sum of these selected elements is equal to

sum/2

Then this problem can be divided into two steps ：

First step , Find the sum of elements within
sum/2
Maximum element sum in case .

The second step , Determine whether the sum of elements is equal to
sum/2
.

For the first step , In fact, it's completely

0-1 knapsack problem

, That is, the maximum capacity of the backpack is

c=sum/2

, The title gives you an array

nums

, Is the capacity of the item , There is a one-to-one relationship between the capacity and value of goods , Under the above restrictions, find the maximum value of the items in the backpack .

State definition ：

We can define a two-dimensional array

dp[i][j]

, The value of this array represents the past

i

Select items , At no more than capacity

j

The maximum total value of the goods .（ notes ： Here's the second

i

Item corresponds to array subscript

i

）

Determine the value of the initial state ：

When there is only one item , If the volume of the article

v

No more than backpack capacity

j

, Then the initial value

dp[0][j]=v

, otherwise

dp[0][j]=0

State transition equation ：

According to the question , For the first

i

Item , Its capacity is

nums[i]

, The value is also

nums[i]

, We can choose this item or not , If you do not select this item, then

, If you choose this item, there are two situations ：

There is not enough space left in the backpack , Then the item cannot be selected at this time ,

.

There is enough space left in the backpack , Then the total value of the goods at this time is

.

Sum up , The equation of state transfer is

Overall problem solving process ：

Find the sum of the elements of the array
sum
, If
sum
For the even , Then go to the next step , Otherwise return to
false
.

Convert to 0-1 knapsack , At a maximum capacity of
sum/2
Under the circumstances , Value and capacity are a one-to-one relationship, seeking the maximum value .

Define the State , Determine the initial transition .

According to the state transfer equation

Calculate the maximum element sum .

Determine whether the maximum element sum is consistent with
sum/2
equal .

Convert to 0-1 Knapsack implementation code ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 int[][] dp = new int[n][c+1];

 for (int j = 0; j <= c; j++) {
 dp[0][j] = j >= nums[0] ? nums[0] : 0;
 }

 for (int i = 1; i < n; i++) {
 for (int j = 0; j <= c; j++) {
 int pre = dp[i-1][j];

 int cur = j >= nums[i] ? dp[i-1][j-nums[i]] + nums[i] : pre;
 dp[i][j] = Math.max(pre, cur);
 }
 }
 // 4. Determine whether the value of the final backpack is equal to sum/2, If equal, it means that it can be divided 
 return dp[n-1][c] == c;
 }
}

Convert to 0-1 knapsack , Rolling array optimization implementation code ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 int[][] dp = new int[2][c+1];

 for (int j = 0; j <= c; j++) {
 dp[0][j] = j >= nums[0] ? nums[0] : 0;
 }

 for (int i = 1; i < n; i++) {
 for (int j = 0; j <= c; j++) {
 int index = (i-1) & 1;
 int pre = dp[index][j];

 int cur = j >= nums[i] ? dp[index][j-nums[i]] + nums[i] : pre;
 dp[i&1][j] = Math.max(pre, cur);
 }
 }
 // 4. Determine whether the value of the final backpack is equal to sum/2, If equal, it means that it can be divided 
 return dp[(n-1)&1][c] == c;

 }
}

Optimized for one-dimensional array implementation code ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 // We found that dp[i][j] Only with dp[i-1][j] and dp[i-1][j-nums[i]] of , We can change the number of remaining spaces from 0-c Traversal changed to c-0 Traverse , Keep only the remaining space dimensions 
 int[] dp = new int[c+1];

 for (int i = 0; i < n; i++) {
 for (int j = c; j >= nums[i]; j--) {
 int pre = dp[j];
 int cur = dp[j-nums[i]] + nums[i];
 dp[j] = Math.max(pre, cur);
 }
 }
 // 4. Determine whether the value of the final backpack is equal to sum/2, If equal, it means that it can be divided 
 return dp[c] == c;
 }
}

️ To divide into equal and subsets ： From no more than to just

Above we are analyzing 【 To divide into equal and subsets 】 when , The problem can be translated into ： Select elements from the array , Each element can only be selected once , Determine whether the sum of these selected elements is equal to

sum/2

Our previous approach is to find out that this does not exceed

sum/2

The largest element and , And then judge , This process is equivalent to 【 Indirect solution 】, In fact, it can not go through the process of solving the maximum element and , It can be solved directly . That is, will ask 【 The question of maximum value 】 Change to seek 【 Whether it is equal to a specific value problem 】.

State definition ：

The state definition of the maximum value problem ：

In front of

Choose from the only items , The total capacity does not exceed

Maximum value of .

Then the definition of whether it is equal to a specific value is ：

In front of

Choose from the only items , Whether the total value is equal to

, The type is

The initial state is determined ：

When only

When an object ,

What is the state of ？ I can only say I'm not sure , Because I don't know

Is it equal to

, Therefore, this state cannot be taken as the initial state .

Here's a trick , That is, we can consider the situation that there are no items to choose as the initial state , Because there is no choice , So the value must be

, that

, Because the state of no object occupies a line , So we need to create one more row in the dynamic return array , And from

The beginning indicates the state of having items , So the first

Items correspond to the array with the subscript

The items .

State transition equation ：

For the first

i

Item , Its value is

nums[i-1]

. If we don't choose it , be

. If we choose it , If

, be

, Otherwise

As long as one of the above two cases is satisfied, the total value is exactly equal to the target value , be

, So the state transfer equation is ：

Implementation code ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 boolean[][] dp = new boolean[n+1][c+1];
 // 4. initialization 
 dp[0][0] = true;

 // 5. Process the remaining states 
 for (int i = 1; i <= n; i++) {
 int val = nums[i-1];
 for (int j = 0; j <= c; j++) {
 // No choice 
 boolean no = dp[i-1][j];
 // choice 
 boolean yes = j >= val ? dp[i-1][j - val] : false;
 dp[i][j] = no || yes;
 }
 }
 return dp[n][c];
 }
}

Rolling array optimization ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 boolean[][] dp = new boolean[2][c+1];
 // 4. initialization 
 dp[0][0] = true;

 // 5. Process the remaining states 
 for (int i = 1; i <= n; i++) {
 int val = nums[i-1];
 for (int j = 0; j <= c; j++) {
 // No choice 
 int index = (i-1) & 1;
 boolean no = dp[index][j];
 // choice 
 boolean yes = j >= val ? dp[index][j - val] : false;
 dp[i&1][j] = no || yes;
 }
 }
 return dp[n&1][c];
 }
}

One dimensional array optimization ：

class Solution {
 public boolean canPartition(int[] nums) {
 int sum = 0;
 // 1. Sum up 
 for (int x : nums) {
 sum += x;
 }
 // 2. If sum is odd , That must not be divided 
 if ((sum & 1) == 1) {
 return false;
 }
 // 3. Convert to 0-1 knapsack 
 int n = nums.length;
 int c = sum / 2;
 boolean[] dp = new boolean[c+1];
 // 4. initialization 
 dp[0] = true;

 // 5. Process the remaining states 
 for (int i = 1; i <= n; i++) {
 int val = nums[i-1];
 for (int j = c; j >= val; j--) {
 dp[j] =dp[j] || dp[j - val];
 }
 }
 return dp[c];
 }
}