LeetCode Day 46 Dynamic Programming (8/17)

Knapsack problem coming to an end! Firstly, today’s practice questions, then the foundation of multiple Knapsack problems, and finally a summary of the Knapsack problems over these days!

1. Practice Question

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

The words are the items, the string s is the knapsack, and whether or not the words can form the string s is a question of whether or not the items can fill up the knapsack.

The fact that words in the dictionary can be reused when splitting suggests that it is a full knapsack!

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False]*(len(s) + 1)
        dp[0] = True 
        for j in range(1, len(s) + 1):
            for word in wordDict:
                if j >= len(word):
                    dp[j] = dp[j] or (dp[j - len(word)] and word == s[j - len(word):j])
        return dp[len(s)]

2. Multiple knapsack problem

This variation is similar to the Bin Packing Problem. It differs from the Bin Packing Problem in that a subset of items can be selected, whereas, in the Bin Packing Problem, all items have to be packed to certain bins. The concept is that there are multiple knapsacks. This may seem like a trivial change, but it is not equivalent to adding to the capacity of the initial knapsack. This variation is used in many loading and scheduling problems in Operations Research and has a Polynomial-time approximation scheme.

There are N items and a knapsack of capacity V . There are at most Mi items of item i available, each of which consumes space Ci and has value Wi . Solve for the items that can be packed into the knapsack so that the sum of the space consumed by these items does not exceed the capacity of the knapsack and the sum of the values is maximised. The Multipack is very similar to the 01 Backpack, why is it similar to the 01 Backpack? Each item has at most Mi pieces available, Mi pieces spread out, in fact, is a 01 Knapsack problem.

But it won’t be tested in the interview, and LeetCode doesn’t have any related questions.

3. Summary of Knapsack problem

Knapsack problem is a very important part of dynamic programming!

3.1 Recursive formula for backpacks

Ask if the backpack can be filled (or at most how much): dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); Ask how many ways to fill the backpack: dp[j] += dp[j - nums[i]] Ask the maximum value of filling the backpack: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ask the minimum number of items to fill the backpack with all items: dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.2 Traversal order

3.2.1 The 01 Backpack

The two-dimensional dp array 01 backpack traverses the items first or the backpack first, and the second level of the for loop is traversed from smallest to largest. The one-dimensional dp array 01 backpack can only traverse items before traversing the backpack capacity, and the second level of the for loop is traversing from large to small. There is a big difference between the traversal order of the one-dimensional dp-array pack and the two-dimensional dp-array 01 pack, which should be noted!

3.2.2 Complete backpacks

If we are looking for combinations, we have an outer for loop that traverses the items, and an inner for that traverses the backpack. If we are looking for the number of permutations, we have an outer for looping through the backpack and an inner for looping through the items. The two most critical parts of the Knapsack problem are the recursive formula and the traversal order.