动态规划 · 0/1 背包与完全背包

def knapsack_01(weights, values, W):
    """0/1 背包：求最大价值。每件物品至多选一次"""
    f = [0] * (W + 1)
    for i in range(len(weights)):
        # 倒序枚举 w：保证 f[w - weights[i]] 还是"上一行"
        for w in range(W, weights[i] - 1, -1):
            f[w] = max(f[w], f[w - weights[i]] + values[i])
    return f[W]


def knapsack_complete(weights, values, W):
    """完全背包：求最大价值。每件物品可选任意次"""
    f = [0] * (W + 1)
    for i in range(len(weights)):
        # 正序枚举 w：允许 f[w - weights[i]] 已包含第 i 个物品
        for w in range(weights[i], W + 1):
            f[w] = max(f[w], f[w - weights[i]] + values[i])
    return f[W]

// 0/1 背包：求最大价值
static int knapsack01(int[] weights, int[] values, int W) {
    int[] f = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        // 倒序枚举 w：保证 f[w - weights[i]] 还是"上一行"
        for (int w = W; w >= weights[i]; w--) {
            f[w] = Math.max(f[w], f[w - weights[i]] + values[i]);
        }
    }
    return f[W];
}

// 完全背包：求最大价值
static int knapsackComplete(int[] weights, int[] values, int W) {
    int[] f = new int[W + 1];
    for (int i = 0; i < weights.length; i++) {
        // 正序枚举 w：允许 f[w - weights[i]] 已包含第 i 个物品
        for (int w = weights[i]; w <= W; w++) {
            f[w] = Math.max(f[w], f[w - weights[i]] + values[i]);
        }
    }
    return f[W];
}

// 0/1 背包：求最大价值
int knapsack01(const vector<int>& weights, const vector<int>& values, int W) {
    vector<int> f(W + 1, 0);
    for (int i = 0; i < (int)weights.size(); i++) {
        // 倒序枚举 w：保证 f[w - weights[i]] 还是"上一行"
        for (int w = W; w >= weights[i]; w--) {
            f[w] = max(f[w], f[w - weights[i]] + values[i]);
        }
    }
    return f[W];
}

// 完全背包：求最大价值
int knapsackComplete(const vector<int>& weights, const vector<int>& values, int W) {
    vector<int> f(W + 1, 0);
    for (int i = 0; i < (int)weights.size(); i++) {
        // 正序枚举 w：允许 f[w - weights[i]] 已包含第 i 个物品
        for (int w = weights[i]; w <= W; w++) {
            f[w] = max(f[w], f[w - weights[i]] + values[i]);
        }
    }
    return f[W];
}

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for j in range(target, x - 1, -1):    # 倒序
                dp[j] = dp[j] or dp[j - x]
            if dp[target]:                          # 提前结束
                return True
        return dp[target]

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if ((total & 1) == 1) return false;
        int target = total >> 1;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums) {
            // 倒序：避免本轮 dp[j-x] 被同轮先更新过的值污染
            for (int j = target; j >= x; j--) {
                if (dp[j - x]) dp[j] = true;
            }
            if (dp[target]) return true;
        }
        return dp[target];
    }
}

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int x : nums) total += x;
        if ((total & 1) == 1) return false;
        int target = total >> 1;

        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int x : nums) {
            // 倒序：避免本轮 dp[j-x] 被同轮先更新过的值污染
            for (int j = target; j >= x; j--) {
                if (dp[j - x]) dp[j] = true;
            }
            if (dp[target]) return true;
        }
        return dp[target];
    }
};

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        INF = amount + 1
        dp = [INF] * (amount + 1)
        dp[0] = 0
        for c in coins:
            for j in range(c, amount + 1):           # 正序
                dp[j] = min(dp[j], dp[j - c] + 1)
        return dp[amount] if dp[amount] <= amount else -1

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = amount + 1;                          // 不能用 Integer.MAX_VALUE
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int c : coins) {
            for (int j = c; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int INF = amount + 1;                          // 不能用 INT_MAX
        vector<int> dp(amount + 1, INF);
        dp[0] = 0;
        for (int c : coins) {
            for (int j = c; j <= amount; j++) {
                dp[j] = min(dp[j], dp[j - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};