Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

one,Two-dimensional array

1、State transfer equation：

• Do not put items: From dp[i - 1][j], that is, when the capacity of the backpack is j and the maximum value of item i is not placed in it, dp[i][j] is dp[i - 1][j]. (In fact, when the weight of item i is greater than the weight of backpack j, item i cannot be put into the backpack, so the value of the backpack remains the same as before.)
• Place items：From dp[i - 1][j - weight[i]], dp[i - 1][j - weight[i]] is the maximum value of not putting item i in the backpack when the capacity is j - weight[i]. Then dp[i - 1][j - weight[i]] + value[i] (the value of item i) is the maximum value of putting item i in the backpack.

So the recursive formula: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

2. Initialization

(1) Based on the definition of dp[i][j], if the backpack capacity j is 0, that is, dp[i][0], no matter which items are selected, the total value of the backpack must be 0.

(2) State transfer equation dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); It can be seen that i is derived from i-1, so when i is 0, it must be initialized.

dp[0][j], that is, when i is 0 and item number 0 is stored, it is the maximum value that a backpack of each capacity can store.

Then it is obvious that when j < weight[0], dp[0][j] should be 0, because the backpack capacity is smaller than the weight of item number 0.

When j >= weight[0], dp[0][j] should be value[0], because the backpack capacity is enough to hold item number 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Other subscript initialization:

  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

dp[1][1] = max(dp[0][1], dp[0][1- weight[i]] + value[i]) must be to its left and above,

Therefore, it must have been initialized and can be set to any value. For convenience, it is initialized to 0 by default.

2. One-dimensional (rolling array)

1. In the one-dimensional dp array, dp[j] means: the value of the items carried by a backpack with a capacity of j can be at most dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Initialization

(1) dp[0] = 0, because the maximum value of the items carried in a backpack with a capacity of 0 is 0.

(2) Assuming that the value of items is greater than 0,In order not to be overwritten by the initial value, so dpArray InitializationWhen

3. Traversal order

Reverse order traversal

Explanation 1: The value at the end of the list needs to be determined by comparing it with the previous value obtained by traversing the previous layer.

Explanation 2: There is only one 01 backpack for each backpack. Whether this bag is put in or not is related to the status of the previous bag. The array on the left is the quantity that describes the status of the previous bag, and the number on the right is a pending number of the current bag status. The code shows that the determination of the right array requires the number on the left, so the number on the left cannot be destroyed before calculating the number on the right.

Explanation 3: For two dimensions, the result of each new dp number comes from the top and the left; in fact, the same should be true for one dimension, but in one dimension, if it is still from left to right, then the number on the left has actually been updated (The left side is no longer the "original" left side! This will cause some double counting), even if the top is still the original top, the number obtained is incorrect. If we traverse from right to left in the backpack layer (inner layer), the elements on the left will always beThe new value will not be overwritten by my previous operation, so that the correct value can be obtained.

3. Application

1. Given a non-empty array containing only positive integers, is it possible to split the array into two subsets so that the sum of the elements of the two subsets is equal?

Note: The number of elements in each array will not exceed 100 and the size of the array will not exceed 200.

Example 1:

• Input: [1, 5, 11, 5]
• Output: true
• Explanation: The array can be split into [1, 5, 5] and [11]

analyze:

The item is i,

The weight is nums[i], the value is also nums[i], and the backpack size is sum/2.

Similar to 01 backpack

State transfer equation:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. There is a pile of stones, and the weight of each stone is a positive integer.

In each round, select any two stones and smash them together. Assume that the weights of the stones are x and y, and x <= y. Then the possible results of the smashing are as follows:

If x == y, then both rocks will be completely crushed;

If x != y, then the rock of weight x will be completely shattered, and the rock of weight y will have a new weight of yx.

At the end, at most one stone will be left. Return the minimum possible weight of this stone. If no stones are left, return 0.

Example:

• Input: [2,7,4,1,8,1]
• Output: 1

analyze:

Try to separate the stones into two piles of equal weight, with the smallest remaining stone after the collision.

Then there are two piles of stones. The total weight of one pile is dp[target], and the total weight of the other pile is sum - dp[target]

When calculating target, target = sum / 2. Because it is rounded down, sum - dp[target] must be greater than or equal to dp[target].

Then the minimum weight of the stone left after the collision is (sum - dp[target]) - dp[target]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

cited from:Code Random Thoughts