2、0-1背包

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.

问最多能装入背包的总价值是多大?

输入: m = 10, A = [2, 3, 5, 7], V = [1, 5, 2, 4]
输出: 9
解释: 装入 A[1] 和 A[3] 可以得到最大价值, V[1] + V[3] = 9 

 https://www.jiuzhang.com/problem/backpack-ii/#tag-lang-python

def bag(m, A, V):
    # 每个物品空间A []
    # 每个物品价值V []
    # m 背包总大小
    # dp[i][j]  # 只用前i个物品，j是剩余容量
    n = len(A)
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if j < A[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - A[i-1]] + V[i-1])
    return dp[n][m]

滚动数组 

class Solution:
    def backPackII(self, m, A, V):
        n = len(A)

        dp = [[0] * (m + 1), [0] * (m + 1)]
        for i in range(1, n + 1):
            dp[i % 2][0] = 0
            for j in range(1, m + 1):
                dp[i % 2][j] = dp[(i - 1) % 2][j]
                if A[i - 1] <= j:
                    dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + V[i - 1])
        return dp[n % 2][m]

1、背包问题（最多能装）

https://www.jiuzhang.com/solutions/backpack/#tag-lang-python

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
输入:  [3,4,8,5], backpack size=10, 输出:  9
输入:  [2,3,5,7], backpack size=12, 输出:  12

用dp[i][j]表示能否用前i个物品拼出重量j (TRUE / FALSE)

开总称重m的数组

class Solution:
    """
    @param m: An integer m denotes the size of a backpack背包大小
    @param A: Given n items with size A[i]物品集合
    @return: The maximum size
    """

    def backPack(self, m, A):
        n = len(A)
        # 用dp[i][j]表示能否用前i个物品拼出重量j (TRUE / FALSE)
        f = [[False] * (m + 1) for _ in range(n + 1)]

        f[0][0] = True
        for i in range(1, m+1):
            f[0][i] = False  # 用前0个物品 不能 拼出重量j

        for i in range(1, n + 1):

            for j in range(0, m + 1):
                if j >= A[i - 1]:
                    f[i][j] = f[i - 1][j] or f[i - 1][j - A[i - 1]]  # 如果不放第i件物品 or 放第i个物品正好凑整j
                else:
                    f[i][j] = f[i - 1][j]  # 如果不放第i件物品

        for i in range(m, -1, -1):  # 从大到小找
            if f[n][i] == True:
                return i

        return 0

weight = 10
A = [3,4,8,5]
s = Solution()
print(s.backPack(weight, A))  # 最多装9

 

2、背包问题 5（填满背包的方案数）

https://www.jiuzhang.com/solutions/backpack-v/

给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 
正整数 target 表示背包的大小, 找到能填满背包的方案数。
每一个物品只能使用一次

给出候选物品集合 [1,2,3,3,7] 以及 target 7
结果的集合为:[7],[1,3,3]
返回 2

优化前

优化后

class Solution:
    """
    @param nums: an integer array and all positive numbers
    @param target: An integer
    @return: An integer
    """
    def backPackV(self, nums, target):
        n = len(nums)
        # 当没有物品时方案数为0
        if n == 0:
            return 0

        # dp[j]组成重量`j`的方案
        dp = [0]*(target + 1)

        # 初始化
        # dp[0][0]=1, dp[0][1]=dp[0][2]...=0
        for i in range(0, target):
            if i == 0:
                dp[i] = 1
            else:
                dp[i] = 0

        for i in range(1, n+1):
            # reverse order!
            for j in range(target, -1, -1):
                if j >= nums[i-1]:
                    # old + old => new
                    dp[j] += dp[j - nums[i - 1]]
        return dp[target]

nums = [1,2,3,3,7]
target = 7
s = Solution()
print(s.backPackV(nums, target))  # 2