【 Backpack problem no.5 】 Strengthen the derivation of the core elements of "complete backpack" by using the characteristics of "equality"

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 backpack-related 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 pre-processing 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:

f[i][j] = min(f[i-1][j-k*t]+k),0 \leqslant k * t \leqslant j

Of course, KKK numbers III can be selected only if the remaining j− K ∗ tj-K * 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 one-dimensional optimization is possible.

So we’re going to do the same thing again, just to strengthen your understanding of this optimization.

Start with the two-dimensional state transition equation for analysis (assuming TTT as the third number) :

So far, we have obtained the final state transition equation:

f[j] = min(f[j], f[j – t] + 1)

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[i-1] = f[i-1] = f[i-1]
                
                // Can update f[j] if the rest of j * t can also be scraped
                // Update f[j] depends on f[j-t] corresponding to the two-dimensional representation of f[i-1][j-k * 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 pre-processing 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” one-dimensional optimization method in the previous section.

Starting from the simple two-dimensional state definition, the state transition equation of one-dimensional 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
1. 01 Backpack: Backpack problem In Lecture 2
2. 01 Backpack: Backpack problem Lecture 3
Complete knapsack: Lecture 4 of the knapsack problem
1. 【 exercise 】 complete backpack: this piece
2. The whole backpack problem Lecture 6
3. Complete knapsack: Knapsack problem Lecture 7
Multiple backpacks: Lecture 8 on the Backpack Problem
Multiple backpacks
1. 【 I 】 Multiple Knapsacks: The Knapsack Problem lecture 9
2. Multiple Knapsack (Optimization) : Knapsack problem lecture 10
Mixed knapsack: The knapsack problem lecture 11
Grouping knapsack: Lecture 12 of the knapsack problem
1. Group packs: Backpack problem Lecture 13
Multidimensional knapsack
1. Multidimensional knapsack: The Knapsack problem Lecture 14
2. Multi-dimensional knapsack: The knapsack problem lecture 15
The Tree Backpack: Lecture 16 on the Backpack Problem
1. A tree backpack
2. A tree backpack
Knapsack solution number
1. 【典型范例 2 】 The number of options is the same as the number of options
Backpack for specific programs
1. 【 practice 】 backpack to find a specific plan
Generalization backpack
1. 【 exercise 】 Generalization backpack

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

【 Backpack problem no.5 】 Strengthen the derivation of the core elements of “complete backpack” by using the characteristics of “equality”

preface

Topic describes

Complete knapsack (Simple solution)

Full backpack (Advanced)

conclusion

Backpack Problem (Table of Contents)

【 Backpack problem no.5 】 Strengthen the derivation of the core elements of “complete backpack” by using the characteristics of “equality”

preface

Topic describes

Complete knapsack (Simple solution)

Full backpack (Advanced)

conclusion

Backpack Problem (Table of Contents)

Related Posts

Conscience recommended! 7 must-read Python books, from Beginner to Master in 3 days

Summary of problems with Layui usage

JavaSE basics: Wrapper classes