preface
Today is the third day of our presentation on the knapsack problem in dynamic programming.
Of all the backpack problems, “01 backpack problem” is the most central, so I recommend you read the backpack problem first lecture carefully before reading this article.
In addition, AT the end of the article, I listed the related topics about the backpack problem that I sorted out.
I will explain the backpack problem in the arranged order (update every 23 days to make sure you digest it).
You can also try to do it first, you are also welcome to leave a message to me, you feel related to backpack DP type topic ~
Topic describes
This is 416 on LeetCode. Split and subset, Medium difficulty.
Given a nonempty array containing only positive integers. Is it possible to split this array into two subsets so that the sum of the elements in the two subsets is equal?
Note:
 There are no more than 100 elements in each array
 The size of the array cannot exceed 200
Example 1:
Input: [1, 5, 11, 5] Output: true Explanation: Arrays can be split into [1, 5, 5] and [11].Copy the code
Example 2:
Input: [1, 2, 3, 5] Output: false Explanation: An array cannot be split into two elements and equal subsets.Copy the code
Fundamental analysis
The basic analysis of “abstracting the original problem into 01 knapsack problem” was discussed in the last lecture
The problem in this section is: how to change the method of “indirect solution” to “direct solution”, and learn why it is possible to do so, and whether there are commonalities between these methods…
Direct solution
Let’s start by reviewing the “state definition” and “transition equation” used in the previous section.
State definition:
F [I][j]f[I][j]f[I][j]f[I][j] represents that the sum of the selected numbers does not exceed the maximum value of JJJ when considering the first three values.
Transfer equation:
But the question is not, “What is the maximum value?” it is, “Can we get the maximum value?”
Therefore, we can modify the state definition of 01 knapsack to make it directly related to our answer:
F [I][j]f[I][j]f[I][j] represents whether the sum of the selected numbers is exactly JJJ considering the previous iii values.
In this case, DPDPDP array stores “Boolean type” moving gauge value.
The corresponding state transition equation can be adjusted as:
∨∨ means “or” in logic.
The new transfer equation represents: f[I][j]f[I][j]f[I][j]f[I][j] (considering the first iii values, the sum of the selected numbers is exactly JJJ) is true. The following two schemes must be met, at least one of which is TrueTrueTrue:
1. $f[i1][j]$(don’t choose the first$i$The sum of the selected numbers is exactly$j$) for$true$
2. $f[i1][jnums[i]]$(choose the first$i$The sum of the selected numbers is exactly$j$) for$true$
So far, using the basic idea of the 01 knapsack, we have modified the “state definition” to relate it directly to the answer, and then adjusted our “transition equation” according to the new “state definition.”
But it’s not over yet.
When we modify the “state definition” of a model, we need to consider modifying the “initialization” state in addition to adjusting the “transition equation.”
Consider that the DPDPDP arrays we create store Boolean values with initial FalseFalse values, which means that no matter how we transfer them, it is impossible to generate a trueTrueTrue, and ultimately all states will still be FalseFalse.
In other words, we also need a valid value trueTruetrue to help recurse.
Usually we use the first line to initialize valid values.
F [0][nums]]=truef[0][nums[0]] =truef[0][nums[0]] =true
F [0][nums[0]]=truef[0][nums[0]] =truef[0][nums[0]] =true indicates that only knapsacks with the capacity of NUMs [0]nums[0]nums[0] meet the requirement of “exactly”.
But we can’t be sure that NUMs [0] NUMs [0]nums[0] won’t exceed our “maximum backpack” capacity (that is, the case where the first item is too big to ever fit in the backpack).
So we’re going to get valid values by processing the next row, right? Or do you prioritize things first?
In fact, one trick here is that we add a “no item” case to the discussion.
Previously our state definition was f[I][j]f[I][j]f[I][j] stands for all items before subscript III. Now we can add the case without considering any items, which is to change the “item number” from 0 to 1.
For 🌰, originally we f [0] [x] f [0] [x] f [0] [x] represent only consider the first item, f [1] [x] f [1] [x] f [1] [x] representatives consider the first and second items; Adjusted our f [0] [x] f [0] [x] f [0] [x] representative does not consider any item, f [1] [x] f [1] [x] f [1] [x] represent only consider the first item…
This technique essentially uses the idea of the sentinel.
With that analysis in mind, and the code base we covered last time, it’s easy to write code.
Although the state definition and transition equation are changed, there are still several implementation methods including “conventional solution”, “rolling array optimization” and “onedimensional space optimization”. Let’s go through this really quickly.
Conventional method
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
// The sum of "equal sum subsets" must be half of the sum
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
// If the sum is odd, it cannot be divided into two equal sum subsets.
if (target * 2! = sum)return false;
// f[I][j] represents a scenario where the value of the previous I items is "exactly" j
boolean[][] f = new boolean[n+1][target+1];
f[0] [0] = true;
for (int i = 1; i <= n; i++) {
int t = nums[i1];
for (int j = 0; j <= target; j++) {
// do not select this item
boolean no = f[i1][j];
// select this item
boolean yes = j >= t ? f[i1][jt] : false; f[i][j] = no  yes; }}returnf[n][target]; }}Copy the code
 Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
 Space complexity: O(n∗target)O(n * target)O(n∗target)
Scroll to the array
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
// The sum of "equal sum subsets" must be half of the sum
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
// If the sum is odd, it cannot be divided into two equal sum subsets.
if (target * 2! = sum)return false;
// f[I][j] represents a scenario where the value of the previous I items is "exactly" j
// Change the item dimension to 2
boolean[][] f = new boolean[2][target+1];
f[0] [0] = true;
for (int i = 1; i <= n; i++) {
int t = nums[i1];
for (int j = 0; j <= target; j++) {
// do not select this item
boolean no = f[(i1) &1][j];
// select this item
boolean yes = j >= t ? f[(i1) &1][jt] : false;
f[i&1][j] = no  yes; }}return f[n&1][target]; }}Copy the code
 Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
 O(Target)O(target)O(target)
Onedimensional space optimization
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
// The sum of "equal sum subsets" must be half of the sum
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
// If the sum is odd, it cannot be divided into two equal sum subsets.
if (target * 2! = sum)return false;
// Remove the item dimension
boolean[] f = new boolean[target+1];
f[0] = true;
for (int i = 1; i <= n; i++) {
int t = nums[i1];
for (int j = target; j >= 0; j) {
// do not select this item
boolean no = f[j];
// select this item
boolean yes = j >= t ? f[jt] : false; f[j] = no  yes; }}returnf[target]; }}Copy the code
 Time complexity: TargettargettarGet is half of the array sum, NNN number of array elements. Denotes that a total of N ∗targetn * targetn∗target states need to be transferred, and the complexity is O(n∗target)O(n * target)O(n∗target)
 O(Target)O(target)O(target)
conclusion
Today we did “416. Segmentation and subsets” again, but from a different Angle:
By modifying 01 knapsack “state definition” and “transfer equation” to achieve “direct solution”.
But is that a particular problem?
Not really. Instead, it’s a generalizable property of the backpack problem:
We can change the “state definition” of a knapsack problem from a maximum of XX capacity to a knapsack capacity of exactly XX, and then set the “valid value construction”, that is, the subscript of the item to start from 1, and set dp[0][0] DP [0][0] DP [0][0]dp[0][0] as the initial value.
This is another kind of “knapsack problem” that doesn’t correspond to “value maximization”, but rather “maximization/specific value”. The “backpack problem” is also common.
We need to master ~
Backpack Problem (Table of Contents)

Knapsack: Knapsack problem first lecture

01 Backpack: Backpack problem In Lecture 2

01 Backpack


Complete knapsack: Lecture 4 of the knapsack problem

Complete backpack: The backpack problem lecture 5

The whole backpack problem Lecture 6

Complete knapsack: Knapsack problem Lecture 7


Multiple backpacks: Lecture 8 on the Backpack Problem

Multiple backpacks

【 I 】 Multiple Knapsacks: The Knapsack Problem lecture 9

Multiple Knapsack (Optimization) : Knapsack problem lecture 10


Mixed knapsack: The knapsack problem lecture 11

Grouping knapsack: Lecture 12 of the knapsack problem
 Group packs: Backpack problem Lecture 13

Multidimensional knapsack

Multidimensional knapsack: The Knapsack problem Lecture 14

Multidimensional knapsack: The knapsack problem lecture 15


The Tree Backpack: Lecture 16 on the Backpack Problem

Lesson 17: The Backpack Problem

A tree backpack


Knapsack solution number
 【 典 型 范 例 2 】 The number of options is the same as the number of options

Backpack for specific programs
 【 practice 】 backpack to find a specific plan

Generalization backpack
 【 exercise 】 Generalization backpack