This is the 12th day of my participation in Gwen Challenge

Topic describes

This is 1449 on LeetCode. Digit cost and maximum number for target value, difficulty is difficulty.

Tag: “Full knapsack”, “Knapsack problem”, “dynamic programming”

I give you an integer array cost and an integer target. Return the maximum integer that satisfies the following rules:

The cost of adding a digit (I + 1) to the current result is cost[I] (cost array subscript starts at 0). The total cost must be exactly equal to Target. There is no 0 in the added digit. Since the answer may be large, please return it as a string.

If you can’t get any integers, return “0”.

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9 output: "7772" explanation: it costs 2 to add digit '7' and 3 to add digit '2'. So the cost of "7772" is 2 times 3 plus 3 times 1, which is 9. "977" is also a good number, but "7772" is the larger number. Digital cost 1 -> 4 2 -> 3 3 -> 2 4 -> 5 5 -> 6 6 -> 7 7 7 -> 2 8 -> 5 9 -> 5Copy the code

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12 Output: "85" Explanation: The cost of adding digit '8' is 7, and the cost of adding digit '5' is 5. The cost of 85" is 7 + 5 = 12.Copy the code

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5 output: "0" explanation: no integer can be generated when the total cost is target.Copy the code

Example 4:

Input: cost =,10,15,40,40,40,40,40,40 [6], target = 47 output: "32211"Copy the code

Tip:

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000

Fundamental analysis

Given a number of numbers between 111 and 999, each of which has a choice cost, what is the maximum number for a given cost?

In general, how do we compare the size of two numbers?

First of all, we compare them according to the length, the longer the length, the larger the number; Furthermore, for the values with the same length, compare them from height to low, and find that the first digit is different, and the value with the larger value of different bits is larger.

Rule 1 has a higher priority than Rule 2.

Based on this, we can construct in two steps.

Dynamic programming + greed

Specifically, first consider the problem of “numerical length”, each number has corresponding selection cost, and the length that can be provided is 111.

The question becomes: if there are several items, what is the maximum value (number of items) that can be chosen if all the expenses are spent, given the cost?

Each number can be selected multiple times and belongs to the full backpack model.

When the maximum “numerical length” is found, consider how to construct the answer.

According to rule two, the highest value should be as large as possible, so we can start at 999 and work our way up to 111, selecting that value if the state can be moved from that value.

PS. I’ve been writing the two-dimensional version for a couple of days now, and I think you’ve all got the hang of it.

Code:

class Solution {
    public String largestNumber(int[] cost, int t) {
        int[] f = new int[t + 1];
        Arrays.fill(f, Integer.MIN_VALUE);
        f[0] = 0;
        for (int i = 1; i <= 9; i++) {
            int u = cost[i - 1];
            for (int j = u; j <= t; j++) {
                f[j] = Math.max(f[j], f[j - u] + 1); }}if (f[t] < 0) return "0";
        String ans = "";
        for (int i = 9, j = t; i >= 1; i--) {
            int u = cost[i - 1];
            while (j >= u && f[j] == f[j - u] + 1) { ans += String.valueOf(i); j -= u; }}returnans; }}Copy the code
  • Time complexity: O(n∗t)O(n * t)O(n∗t)
  • Space complexity: O(t)O(t)O(t)

Think & Advance

If you think about it in two steps, it’s pretty easy. It is DP + greed, but both parts are easy.

In fact, there are several versions of this question that can be derived by changing the conditions/ideas:

  1. 【 thinking 】 how to completely transform into “01 backpack” or “multiple backpack” to deal with?

    The time complexity of the complete backpack after one-dimensional optimization is O(N∗C)O(N * C)O(N∗C). Is it possible to convert the problem to two other traditional backpacks by preprocessing items without exceeding this complexity?

    • The answer to “multiple packs” is yes. Given the final cost TTT, we can explicitly calculate the maximum number of times each item can be selected, and we can preprocess an additional array of S []s[] S [] within the complexity of O(N)O(N)O(N). Then, with “monotone queue optimization”, the complexity of O(N∗C)O(N * C)O(N∗C) is achieved, so that the overall complexity will not be worse. But the conversion increases the computation of “pre-processing”. In order to make the conversion “meaningful”, we can make a small optimization during the “preprocessing” : for the same cost number, only keep the high number. It’s not hard to show that choosing a larger number doesn’t make the result worse when you’re doing the same thing.

    • For the 01 backpack, the answer is no. The reason is the same as the simple conversion of “multiple knapsack” to “01 knapsack” does not reduce complexity. Therefore, in this case, changing to “01 knapsack” will cause NNN to increase at the nontrivial level.

  2. Advanced is no longer a given value
    1 1     ~
    9 9     (cancel
    c o s t cost     Array), converted to a given
    n u m s nums     Array (represents the number that can be selected, not included
    0 0     ), and corresponding
    p r i c e price     Array (length and
    n u m s nums     Consistency means choice
    n u m s [ i ] nums[i]     The cost consumed is zero
    p r i c e [ i ] price[i]     ). Will existing practices fail?

    Numsnumsnums no longer has a value of length 111. But our two rules for determining the size of a value remain the same. So step 1 doesn’t need to be adjusted, but before step 2 begins, we need to make sure that the greedy answer construction process is correct by sorting items in a “custom rule”. The rules and the proofs are not hard so think for yourself.

  3. Advanced In advanced
    1 1     On the premise that is allowed
    n u m s nums     appear
    0 0     And make sure the answer has a solution (no answer is returned
    0 0     ), how to solve it?

    Increasing the value of 000 only affects the decision on the highest digit.

    We can convert it to “group&tree” knapsack problem by preprocessing: numsnumsnumS non-000 as a set of “main” (grouping knapsack part: one main must be selected), all values as “accessory” (tree knapsack part: several can be selected, the accessory must be selected at the same time).

Backpack Problem (Table of Contents)

  1. Knapsack: Knapsack problem first lecture

    1. Lesson 2 (416. Segmentation and Subsets)

    2. Lesson 3 (416. Segmentation and Subsets)

  2. Complete knapsack: Lecture 4 of the knapsack problem

    1. Perfect Knapsack problem Lecture 5 (279. Perfect Squares)

    2. Lesson 6 (322. Small Change)

    3. Lesson 7 (518. Change FOR II)

    4. Lecture 1 (1449. Digital cost and maximum number for target value)

  3. Multiple backpacks: Lecture 8 on the Backpack Problem

  4. Multiple backpacks

    1. Multiple Knapsacks: The Knapsack problem lecture 9

    2. Multiple Knapsacks: The Knapsack problem lecture 10

  5. Mixed backpack

    1. Mix the backpack

  6. Packet backpack

    1. 【 exercise 】 Pack in groups

  7. Multidimensional knapsack

    1. Lesson 1 (474. Ones and Zeros)
    2. Lecture * (879. Profit Planning)

  8. The tree backpack

    1. A tree backpack

  9. Knapsack solution number

    1. Lesson 1 (494. Goals and Sums)
    2. Lecture * (879. Profit Plan)

  10. Backpack for specific programs

    1. 【 典 型 范 例 】 Backpack: backpack problem first lecture (1049. The weight of the last stone II)
    2. 【 典 型 范 例 】 Knapsack problem: knapsack problem Digit cost and maximum number for target value)

  11. Generalization backpack

    1. 【 exercise 】 Generalization backpack

The last

This is the No.1449 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.