Full Resolution of Knapsack Problem

takeaway

Knapsack Problem is a very classic type of dynamic programming. The general solution idea is as follows: the maximum total value of items in the state before I can be loaded under the backpack with capacity J, and then the capacity of items and backpack is traversed, and the current state is constantly updated according to the previous state. This paper is the follow-up to the full analysis of Knapsack problem (part 1), and mainly analyzes several examples of Knapsack problem solution in Leetcode.

Related topics

322. Change: Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1.

The solution is as follows: let dp[I] represent the minimum number of coins to fill up the i-yuan, traverse all coins, and the transfer equation is dp[I] = min(dp[I], dp[i-c]+1).

var coinChange = function (coins, amount) {
    let dp = Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (let c of coins) {
            if (i - c >= 0) {
                dp[i] = Math.min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};
Copy the code

Input: Array = {" 10 ", "0001", "111001", "1", "0"}, m = 5, n = 3 output: 4: A total of four strings can be spelled with five zeros and three ones: "10","0001","1","0".Copy the code

Define dp[I][j][k] to represent the maximum number of strings that can be sprouted by giving I zeros and J ones for the first k strings. For the current string, we can choose to spell or not spell, and the transition equation is as follows, where we assume that the current string requires a 0 and b 1,

dp[i][j][k] = Math.max(dp[i-a][j-b][k-1]+1,dp[i][j][k-1])
Copy the code

The code is as follows:

/** * @param {string[]} strs * @param {number} m * @param {number} n * @return {number} */ var findMaxForm = function(strs, m, n) { let len = strs.length; let dp = Array(m+1).fill().map(()=>Array(n+1).fill().map(()=>Array(len).fill(0))); // let count = []; // Let count = []; for(let i=0; i<strs.length; i++){ let cur = strs[i]; Let TMP = [0, 0]; for(let k=0; k<cur.length; k++){ if(cur[k] === "0"){ tmp[0]++; }else{ tmp[1]++; } } count.push(tmp); } for(let k=1; k<=len; k++){ for(let i=0; i<=m; i++){ for(let j=0; j<=n; j++){ let [a,b] = count[k-1]; dp[i][j][k] = dp[i][j][k-1]; if(i - a >= 0 && j - b >= 0){ dp[i][j][k] = Math.max(dp[i][j][k],dp[i-a][j-b][k-1]+1); } } } } return dp[m][n][len]; };Copy the code

494. Target sum: Given an array of non-negative integers, A1, A2… An and a target number, S. Now you have two symbols plus and minus. For any integer in the array, you can add a symbol from + or – to the front of it. Returns the number of methods that can make the final array and add symbols to the target number S.

Input: nums: [1, 1, 1, 1], S: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1+1+1 = 3 +1+1+1+1 = 3 +1+1+1+1 +1 = 3 there are 5 ways to get the final sum to be 3.Copy the code

If you think of the + here as taking something out of the backpack problem, and the minus here as not taking something out of the backpack problem, the only difference is that if you don’t take something out of the backpack problem, you’re subtracting the weight of the item. Since the subtraction operation is introduced, the resulting value can be negative, ranging from -sum (nums), the negative value of the sum of items, to + sum(nums). So our state is defined as dp[I][j] for the first I numbers, and the result is the number of species j. J can be a negative number here, and using dictionaries instead of arrays in code implementation can avoid negative subscripts. The transfer equation is:

dp[i][j] += dp[i-1][j-nums[i-1]]
dp[i][j] += dp[i-1][j+nums[i-1]]
Copy the code

In the initial case, dp[0][0] = 1, which means that when the sum of the components is 0, there is one solution. The complete code is as follows:

var buildDict = function (sum) { let dict = {}; for (let i = -sum; i <= sum; i++) { dict[i] = 0; } return dict; }; Dp [1][-a], Var findTargetSumWays = function (nums, S) {let sum = nums.reduce((S, n) => S + n, 0); let n = nums.length; let dp = Array(2).fill().map(() => buildDict(sum)); dp[0][0] = 1; for (let i = 1; i <= n; i++) { dp[i % 2] = buildDict(sum); for (let j = -sum; j <= sum; j++) { if (j - nums[i - 1] >= -sum) { dp[i % 2][j] += dp[(i - 1) % 2][j - nums[i - 1]]; } } for (let j = sum; j >= -sum; j--) { if (j + nums[i - 1] <= sum) { dp[i % 2][j] += dp[(i - 1) % 2][j + nums[i - 1]]; } } } return dp[n % 2][S] ? dp[n % 2][S] : 0 };Copy the code

139. Word splitting: Given a non-empty string S and a wordDict containing non-empty words, determine whether S can be split by Spaces into one or more words that appear in the dictionary. Note: You can reuse the words in the dictionary when splitting. You can assume that there are no duplicate words in the dictionary.

Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Returns true because "applepenapple" can be split into "applepenapple".Copy the code

If dp[I] is true, then it must be transferred from one of the preceding states where dp[j] is true. And satisfy the string from j -> I (before closed after open interval, as substring method) in the dictionary. So here’s the code

var wordBreak = function (s, wordDict) { let set = new Set(wordDict); let maxLen = Math.max(... wordDict.map(item => item.length)); let dp = Array(s.length + 1).fill(false); dp[0] = true; for (let i = 1; i <= s.length; i++) { for (let j = i - 1; j >= i - maxLen; j--) { if (set.has(s.substring(j, i))) { dp[i] = dp[j] || dp[i]; } } } return dp[s.length] };Copy the code

All topics and links

Ok,

1. 92. Backpack problem

2. 125. Backpack problem II

3. 440. Backpack problem III

4. 798. Backpack problem VII

5. 562. Backpack problem IV

6. 564. Sum of combinations IV

7. 563. Knapsack problem V

8. 799. \ [knapsack problem ix] (https://www.lintcode.com/problem/backpack-viii/description)

9. 800. \ [knapsack problem IX] (https://www.lintcode.com/problem/backpack-ix/description)
10. 801. \ [knapsack problem X] (https://www.lintcode.com/problem/backpack-x/description)

</div>
Copy the code

11. \ [971. Surplus value backpack] (https://www.lintcode.com/problem/surplus-value-backpack/description)

</div>
Copy the code

12. \ [1382. Large capacity backpack] (https://www.lintcode.com/problem/high-capacity-backpack/description)

The next

1. 322. Change

2. 474. One and zero

3. 494. The target and

4. 139. Word split