background

Recently I saw such a pen test:

You order X take out and select a restaurant, and you have a full x dollar minus 10 yuan voucher in your hand. There are n kinds of dishes in the store, and one serving of the I type dish costs Ai yuan. Since you don’t want to eat too many servings of the same dish, you can only order one serving of each dish at most. Now ask you what is the minimum amount of goods you need to choose to use this coupon.

[input description] the two positive solutions n and x in the first line respectively represent the number of dishes and the lowest price of coupons (1<=n<= 199,1 <=x<=1000). The second line is an array of integers, the ith integer representing the price of the ith dish (I <= Ai<= 100). [Output Description] A number, indicating the minimum number of dishes that need to be selected to use the coupon of x yuan minus 10 yuan, ensuring that there is a solution.

[e.g.]
input 5 20 
output 18 19 17 6 7
Copy the code

Analysis of the

First of all, it doesn’t matter how many dollars we subtract from this coupon, it’s all about how much we subtract from it (too real to count in an array… Why does that sound so familiar? Ah! It’s the backpack.

How to solve the backpack problem

The classical solution to the backpack problem is dynamic programming: set the ith item weight as W[I], value as C[I], backpack capacity as J, dp[I][j] represents the maximum value when the ith item is selected and the backpack capacity is J. [Key points of the transfer equation] Imagine the moment when you put in the I item:

  • ifW[i] > jWe can’t carry this. Throw it away

  • ifW[i] < jWe can try to memorize this thing (^o^)/

    • If not, thendp[i][j] = dp[i - 1][j](Because the distance doesn’t change)
    • If back, thendp[i][j] = dp[i - 1][j - W[i]] + C[i]

What does dp[i-1][j-w [I]] mean?

The essence of the knapsack problem is to find the maximum value in the set of all combinations satisfying a certain condition. (CR: Yan DP method)

Does not containiIs in thei - 1Choose the best combination of these numbers;

containsiIs in theiThis number is fixed (i.eiThis element must have), inj - W[i]Under the restriction ofi - 1Choose the best combination of these numbers.

const weights = [1.3.5.7];
const values = [2.5.2.5];
const volume = 8;

let dp = [];
dp[-1] = new Array(volume + 1).fill(0); // Get dp[-1][...]
for (let i = 0; i < weights.length; i++) {
  dp[i] = []; // Create a new column
  for (let j = 0; j <= volume; j++) {
    dp[i][j] = dp[i - 1][j];
    if (weights[i] < volume) {
      // Does not exceed the total capacity
      Dp [I][j] dp[I][j]
      dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i]] + values[i]); }}}return dp[weights.length - 1][volume];
Copy the code

To optimize the

The optimization of DP problems generally starts from space, and the key point is to observe [dependence]. Recall Fibonacci’s DP solution, since the current value only depends on the first two numbers, you only need to record the first two numbers in a sliding window. In the case of two-dimensional arrays, it’s important to think about the process of filling a table in a two-dimensional array. We update the table row by row/column by column, not overwriting the previous values. After the dimension reduction strike, each update overwrites the previous one. Going back to the knapsack problem, the current value of I depends on the value of I minus 1, and we can use the value saved in the last update to update this rotation.

for (let i = 0; i < weights.length; i++) {
  dp[i] = []; 
  for (let j = 0; j <= volume; j++) {
    dp[j] = dp[j];
    // Equivalent to dp[I][j] = dp[i-1][J];
    // Because this time dp[j] is the last round I (i.e. I - 1) j value
    if (weights[i] <= volume) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
      / / whether the equivalent (dp [I] [j], dp [I - 1] [j - weights [I]] + values [I])?
      // select * from 'p' where 'p' = 'p'
      // j-weights [I] uses the values before j, which have been updated in this round
      // So now the whole expression is equivalent to
      // (dp[i][j], dp[i][j - weights[i]] + values[i])}}}Copy the code

If the j is updated in reverse order, the j-weights [I] is used for the i-1 round. Also, if (weights[I] <= volume) can be moved to the loop condition.

// Correct version
for (let i = 0; i < weights.length; i++) {
  dp[i] = []; 
  for (let j = volume; j >= weights[i]; j++) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    // (dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])}}}Copy the code

Back to the delivery

When ordering takeout, we’re looking for the lowest value in a set greater than a certain price. Convert into a backpack problem to find the [maximum] complement of selected dishes, which cannot exceed the [total value of dishes – threshold of full reduction]. Let the ith dish price be P[I], dp[I][j] means that the ith thing is selected, and the complement size limit is J. When choosing dish I:

  • If NOT, thendp[i][j] = dp[i - 1][j](Because the distance doesn’t change)
  • If want to, thendp[i][j] = dp[i - 1][j - P[i]] + P[i]

So once we figure out what the maximum complement is, we’re going to find the minimum value in the set greater than a certain price.