preface
Today is the fifth day of our presentation on the knapsack problem in dynamic programming.
Starting with this post, we will complete three full backpackrelated practice questions, so hang in there.
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 order it is arranged (update every few 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 LeetCode 279. Perfect square, Medium difficulty.
Given a positive integer NNN, find several perfect squares (e.g. 1, 4, 9, 16…). So that their sum is equal to NNN.
You want to minimize the number of perfect squares that make up the sum.
Given an integer NNN, return the sum as the “minimum number” of perfect squares of NNN.
A perfect square is an integer whose value is equal to the square of another integer; In other words, its value is equal to the product of an integer.
For example, 1, 4, 9, and 16 are perfect squares, but 3 and 11 are not.
Example 1:
Input: n = 12 Output: 3 Description: 12 = 4 + 4 + 4Copy the code
Example 2:
Input: n = 13 Output: 2 Description: 13 = 4 + 9Copy the code
Tip:
 1 <= n <= $10^4$
Complete knapsack (Simple solution)
First of all, there’s an infinite number of perfect squares, but the number we’re trying to make up is given.
Therefore, in the first step, we can preprocess the “perfect squares” within the range of [1,n][1, n].
This step is basically preprocessing all the possible numbers.
At the same time, we can only use the same “perfect square number” once because the problem does not limit us.
So our question becomes:
Given a number of numbers, each number can be used an infinite number of times to find the target value$n$What you need is the minimum number of digits.
This clearly fits the “full backpack” model.
The original state definition of the two types of knapsack problems we have studied so far (01 knapsack & full knapsack) is two dimensions:

The first dimension iii represents the item number

The second dimension, JJJ, represents the capacity
The second dimension JJJ has two definitions: “no more than capacity JJJ” and “capacity just as JJJ”.
And they want us to find the minimum number that we need to get exactly NNN.
So we can adjust our “state definition” :
$f[i][j]$To consider before$i$Two numbers, sum them up$j$The minimum number of numbers required.
Without loss of generality, f[I][j]f[I][j]f[I][j]f[I][j]f[I][j] for the third number (assuming TTT), we have the following choices:

Choose zero digital iii, there are f [I] [j] = f [I – 1) [j] [I] [j] f = f [I – 1) [j] [I] [j] f = f [I – 1) [j].

Choose a digital iii, there are f [I] [j] = f [I – 1) [j] – t + 1 f [I] [j] = f [I – 1) [j] – t + 1 f [I] [j] = f [I – 1) [j] – t + 1

Choose two digital iii, there are f [I] [j] = f [I – 1) [j] – 2 ∗ t + 2 f [I] [j] = f [I – 1) [j] – 2 * t + 2 f [I] [j] = f [I – 1) [j] – 2 ∗ t + 2
.
 Choose k digital iii, there are f [I] [j] = f [I – 1) [j] – k ∗ t + kf [I] [j] = f [I – 1) [j] – k * t + kf [I] [j] = f [I – 1) [j] – k ∗ t + k
Therefore, our state transition equation is:
Of course, KKK numbers III can be selected only if the remaining j− K ∗ tjK * Tj − K ∗t can also be rounded out by other “perfect squares”, The f [I – 1) [j] – k ∗ t f [I – 1] [j] – k * t f [I – 1) [j] – k ∗ t for meaningful value.
Code:
class Solution {
int INF = 1;
public int numSquares(int n) {
// Preprocess all possible "perfect squares"
List<Integer> list = new ArrayList<>();
int idx = 1;
while (idx * idx <= n) {
list.add(idx * idx);
idx++;
}
// f[I][j] represents the minimum number of elements used by j by considering the first I items
int len = list.size();
int[][] f = new int[len][n + 1];
// handle the first case
for (int j = 0; j <= n; j++) {
int t = list.get(0);
int k = j / t;
if (k * t == j) { // If the capacity is an integer multiple of the first number, it can be collected
f[0][j] = k;
} else { // The rest are invalid values
f[0][j] = INF; }}// Handle the rest of the case
for (int i = 1; i < len; i++) {
int t = list.get(i);
for (int j = 0; j <= n; j++) {
// For the case where the ith number is not chosen
f[i][j] = f[i  1][j];
// For k th th
for (int k = 1; k * t <= j; k++) {
// Can select k t if the rest of the numbers j  k * t can also be rounded
if (f[i  1][j  k * t] ! = INF) { f[i][j] = Math.min(f[i][j], f[i 1][j  k * t] + k); }}}}return f[len  1][n]; }}Copy the code
 Time complexity: Preprocessing all possible digital complexity is O(n)O(\ SQRT {n})O(n), a total of N ∗nn * \ SQRT {n}n∗ N states need to be transferred, and each state transfer is traversed NNN times at most. Therefore, after all states are transferred, the complexity is O(n2∗n)O(n^2 * \ SQRT {n})O(n2∗n). The overall complexity is O(n2∗n)O(n^2 * \ SQRT {n})O(n2∗n).
 Space complexity: O(n∗n)O(n * \ SQRT {n})O(n∗n).
Full backpack (Advanced)
Obviously the naive version of the full knapsack is a little bit more complicated.
In the last video on full knapsack, we deduced from a “mathematical” point of view why onedimensional optimization is possible.
So we’re going to do the same thing again, just to strengthen your understanding of this optimization.
Start with the twodimensional state transition equation for analysis (assuming TTT as the third number) :
So far, we have obtained the final state transition equation:
Code:
class Solution {
int INF = 1;
public int numSquares(int n) {
// Preprocess all possible "perfect squares"
List<Integer> list = new ArrayList<>();
int idx = 1;
while (idx * idx <= n) {
list.add(idx * idx);
idx++;
}
// f[j] represents the minimum number of elements used by j, taking into account the current item
int len = list.size();
int[] f = new int[n + 1];
// handle the first case
for (int j = 0; j <= n; j++) {
int t = list.get(0);
int k = j / t;
if (k * t == j) { // If the capacity is an integer multiple of the first number, it can be collected
f[j] = k;
} else { // The rest are invalid valuesf[j] = INF; }}// Handle the rest of the case
for (int i = 1; i < len; i++) {
int t = list.get(i);
for (int j = t; j <= n; j++) {
// f[i1] = f[i1] = f[i1]
// Can update f[j] if the rest of j * t can also be scraped
// Update f[j] depends on f[jt] corresponding to the twodimensional representation of f[i1][jk * t]
if(f[j  t] ! = INF) f[j] = Math.min(f[j], f[j  t] +1); }}returnf[n]; }}Copy the code
 Time complexity: the complexity of all possible numbers used for preprocessing is O(n)O(\ SQRT {n})O(n), and a total of N ∗nn * \ SQRT {n}n∗n states need to be transferred, and the complexity is O(n∗n)O(n * \ SQRT {n})O(n∗n). The overall complexity is O(n∗n)O(n * \ SQRT {n})O(n∗n).
 Space complexity: O(n)O(n)O(n).
conclusion
Today, we strengthen the ergodic sequence derivation of the “complete knapsack” onedimensional optimization method in the previous section.
Starting from the simple twodimensional state definition, the state transition equation of onedimensional space is deduced step by step, and the ergodic order is determined from the state transition equation.
As you can see, this question differs from our traditional definition of a “full backpack” state:
The traditional definition of a “complete knapsack” state asks us to find the maximum value, whereas the problem asks us to find the minimum number of elements needed to achieve a value.
But the model is still the “full backpack” model of “each item can be selected indefinitely, and each item selected carries a corresponding value and cost.”
I suggest you take a look at what we saw in the last video.
Backpack Problem (Table of Contents)

Knapsack: Knapsack problem first lecture

01 Backpack: Backpack problem In Lecture 2

01 Backpack: Backpack problem Lecture 3


Complete knapsack: Lecture 4 of the knapsack problem

【 exercise 】 complete backpack: this piece

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

A tree backpack

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