Leetcode knapsack problem

Power button https://leetcode-cn.com/problems/coin-change/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-wan-q-80r7/

Take you through 01 knapsack problem （ Scroll through the array ） | Since then, I am no longer confused about the knapsack problem ！_ Bili, Bili _bilibili

01 backpack theory

A two-dimensional dp

A one-dimensional dp 

  reflection

1. Why one dimension dp To flashback traversal

Because two-dimensional dp The upper and lower floors are separated from each other , It doesn't affect each other . A one-dimensional dp Influence between front and back , Only flashback traversal .

Completely backpack

Random code recording Identify code Capriccio , Learning algorithms don't get lost https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85

Objectives and

01 knapsack

class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        sumValue = sum(nums)
        if target > sumValue or (sumValue + target) % 2 == 1 or (abs(target) > sumValue): 
            return 0
        bagSize = (sumValue + target) // 2
        dp = [0] * (bagSize + 1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(bagSize, nums[i] - 1, -1):
                dp[j] += dp[j - nums[i]]
        return dp[bagSize]

474. One and zero

01 knapsack

  Random code recording Identify code Capriccio , Learning algorithms don't get lost https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]	#  Default initialization 0
        #  Traverse the items 
        for str in strs:
            ones = str.count('1')
            zeros = str.count('0')
            #  Traverse the backpack capacity and traverse from back to front ！
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        return dp[m][n]

518 Change for 2 

Completely backpack