01背包 完全背包

01背包 完全背包

出自灵神的算法精讲

回溯三问

• 当前操作：枚举第i个物品选或者不选：不选，剩余容量不变；选：剩余容量减少v[i]
• 子问题：在剩余容量为c时，从前i个物品中得到的最大价值和
• 下一个子问题 ：分类讨论
  • 不选，在剩余容量为c时， 从前i - 1个物品中得到的最大价值和
  • 选，在剩余容量为c - w[i]时，从前i - 1个物品中得到的最大价值和
    dsf(i, c) = max(dfs(i - 1, c), dfs(i - 1, c - v[i]) + w[i]

代码

# 01背包
def dfs(i, c):
    if i < 0: 
        return 0
    if c < v[i]:
        return dfs(i - 1, j)
    return max(dfs(i - 1, c), dfs(i - 1 c - v[i]) + w[i])
return dfs(n - 1, capacity) 

对应例题：目标和
ac_coder

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target //= 2

        @cache
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            if c < nums[i]:
                dfs(i - 1, c)
            return dfs(i - 1, c) +  dfs(i - 1, c - nums[i])
        return dfs(n - 1, target)
        

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        for (auto c: nums) target += c;
        if (target % 2 || target < 0) return 0;
        target /= 2;

        int n = nums.size(), cache[n][target + 1];
        memset(cache, -1, sizeof cache);
        function<int(int, int)> dfs = [&](int i, int c) -> int {
            if (i < 0) return c == 0;
            int &res = cache[i][c];
            if (res != -1) return res;
            if (c < nums[i]) return dfs(i - 1, c);
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i]);
        };

        return dfs(n - 1, target);
    }
};