72. 背包问题.md

我们有一个背包，背包总的承载重量是 Wkg。现在我们有 n 个物品，每个物品的重量不等，并且不可分割。我们现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

class Solution:
    def bag(self, items: List[int], capacity:int) -> List[List[int]]:
        ind = 0
        cur = 0
        max_weight = 0
        n = len(items)
        #构造递归
        def dfs(ind, cur):
            #递归终止条件
            if ind == n:
                if cur > max_weight:
                    max_weight = cur
                return
            #情况1
            if cur+items[ind] <= capacity:
                dfs(ind+1, cur+items[ind])
            #情况2
            dfs(ind+1, cur)
        #调用递归
        dfs(ind, cur)
        #返回要优化的目标
        return max_weight