[Algo] 零一背包

1. 夏季特惠

// 1. 夏季特惠
// https://leetcode.cn/problems/tJau2o/description/
long maxHappyValue(vector<long> &a, vector<long> &b, vector<long> &w, long x)
{
    // a: 原价数组, b: 现价数组, w: 快乐值数组, x: 预算
    long n = a.size();
    vector<long> diff(n);
    for (long i = 0; i < n; i++) diff[i] = a[i] - 2 * b[i];
    // diff[i] >= 0: 直接购买(提高预算), diff[i] < 0: 01背包
    long ans = 0;
    vector<long> val, cost;
    for (long i = 0; i < n; i++)
    {
        if (diff[i] >= 0) 
        {
            ans += w[i];
            x += diff[i];
        }
        else
        {
            val.push_back(w[i]);
            cost.push_back(-1 * diff[i]);
        }
    }

    long m = val.size();
    vector<vector<long>> dp(m + 1, vector<long>(x + 1)); // dp[i][j]: 用前i个物品容量不超过j获得的最大价值
    for (long i = 1; i <= m; i++)
    for (long j = 0; j <= x; j++)
    {
        long p1 = dp[i - 1][j], p2 = 0;
        if (j >= cost[i - 1]) p2 = val[i - 1] + dp[i - 1][j - cost[i - 1]];
        dp[i][j] = max(p1, p2);
    }
    ans += dp[m][x];
    return ans;
}

2. 目标和

// 2. 目标和
// https://leetcode.cn/problems/target-sum/
int findTargetSumWays(vector<int>& nums, int target) {
    // 原问题等价于将nums分为两个子集A和B, 使得sum(A) - sum(B) = target
    // 由于sum(A) + sum(B) = sum(nums), 可得sum(A) = (target + sum(nums)) / 2
    // 问题转化为01背包问题: 从nums中选取若干个数, 使得其和等于(target + sum(nums)) / 2的方案数
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum < target || (sum + target) % 2 == 1) return 0;
    int n = nums.size(), m = (sum + target) / 2;
    if (m < 0) return 0;

    vector<vector<int>> dp(n + 1, vector<int>(m + 1)); // dp[i][j]: 前i个数和为j的方案数
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
    {
        dp[i][j] = dp[i - 1][j];
        if (j >= nums[i - 1]) dp[i][j] += dp[i - 1][j - nums[i - 1]];
    }
    return dp[n][m];
}

3. 最后一块石头的重量

// 3. 最后一块石头的重量
// https://leetcode.cn/problems/last-stone-weight-ii/description/
int lastStoneWeightII(vector<int>& stones) {
    // 原问题等价于将stones分为两个子集A和B, 使得|sum(A) - sum(B)|最小
    // 问题转化为01背包问题: 从stones中选取若干个数, 使得其和尽可能接近但不超过sum(stones) / 2
    int sum = 0;
    for (int stone : stones) sum += stone;
    int n = stones.size(), m = sum / 2;
    vector<vector<int>> dp(n + 1, vector<int>(m + 1)); // dp[i][j]: 前i个数中累加和尽可能接近但不超过j的累加和
    // dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1])
    for (int i = 1; i <= n; i++)
    for (int j = 0; j <= m; j++)
    {
        dp[i][j] = dp[i - 1][j];
        if (stones[i - 1] <= j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
    }
    return sum - 2 * dp[n][m];
}

4. 购物单(有依赖的背包问题)

// 4. 购物单(有依赖的背包问题)
// https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
int maxContentValue(int n, int m, vector<int> &v, vector<int> &w, vector<int> &q) {
    // n: 预算, m: 物品数量, v: 价格, w: 重要度, q: 主商品编号
    // 根据主商品进行动态规划
    vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // dp[i][j]: 0...i物品, 预算不超过j的总价值
    vector<bool> isMain(m + 1, false); // 是否为主商品
    vector<vector<int>> sub(m + 1, vector<int>(0)); // 子商品列表
    for (int i = 1; i <= m; i++)
    {
        w[i] = w[i] * v[i]; // 重要度转化为价值
        if (q[i] == 0) isMain[i] = true;
        else sub[q[i]].push_back(i);
    }

    int pre = 0; // 前一个主商品
    for (int i = 1; i <= m; i++)
    {
        if (!isMain[i]) continue;
        for (int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[pre][j]; // 可能性1: 不选当前主商品
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[pre][j - v[i]] + w[i]); // 可能性2: 选当前主商品
            int fan1 = sub[i].size() >= 1 ? sub[i][0] : -1;
            int fan2 = sub[i].size() >= 2 ? sub[i][1] : -1;
            if (fan1 != -1 && j >= v[i] + v[fan1]) 
            dp[i][j] = max(dp[i][j], dp[pre][j - v[i] - v[fan1]] + w[i] + w[fan1]); // 可能性3: 选当前主商品和第一个子商品
            if (fan2 != -1 && j >= v[i] + v[fan2]) 
            dp[i][j] = max(dp[i][j], dp[pre][j - v[i] - v[fan2]] + w[i] + w[fan2]); // 可能性4: 选当前主商品和第二个子商品
            if (fan1 != -1 && fan2 != -1 && j >= v[i] + v[fan1] + v[fan2]) 
            dp[i][j] = max(dp[i][j], dp[pre][j - v[i] - v[fan1] - v[fan2]] + w[i] + w[fan1] + w[fan2]); // 可能性5: 选当前主商品和两个子商品
        }
        pre = i;
    }
    return dp[pre][n];
}