多重背包-二进制优化

别抄

#include<bits/stdc++.h>
using namespace std;

// 定义最大物品数量和背包容量，根据题目数据范围调整
// dp[j]表示容量为j时的最大价值
// w[i]和v[i]分别存储拆分后第i个物品的重量和价值
long long dp[114514], w[114514], v[114514];

int main(){
    // tot用于记录二进制拆分后生成的新物品总数
    int tot = 0;
    int n, c;
    
    // 输入物品数量n和背包总容量c
    cin >> n >> c;
    
    // 遍历每一种原始物品
    for(int i = 1; i <= n; i++){
        int weight, value, k;
        // 输入当前物品的单件重量、单件价值和数量
        cin >> weight >> value >> k;
        
        // 二进制拆分核心逻辑：
        // 将数量k拆分为 1, 2, 4, ..., 2^m, remainder
        // 这样可以通过选取这些拆分项的组合，表示1到k之间的任意数量
        for(int j = 1; j <= k; j *= 2){
            // 生成一个新物品，其重量为 j * weight，价值为 j * value
            w[++tot] = j * weight;
            v[tot] = j * value;
            // 从剩余数量中减去已拆分的部分
            k -= j;
        }
        
        // 如果还有剩余数量（即k不能正好被2的幂次完全分解）
        // 将剩余部分作为一个独立的物品加入
        if(k){
            w[++tot] = k * weight;
            v[tot] = k * value;
        }
    }
    
    // 0/1背包动态规划过程
    // 遍历所有拆分后生成的新物品
    for(int i = 1; i <= tot; i++){
        // 逆序遍历背包容量，确保每个拆分后的物品只被使用一次（0/1背包特性）
        // j从最大容量c递减到当前物品的重量w[i]
        for(int j = c; j >= w[i]; j--){
            // 状态转移方程：
            // dp[j] = max(不选当前物品, 选当前物品)
            // 如果选当前物品，则价值为 dp[j - w[i]] + v[i]
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    // 输出容量为c时的最大价值
    cout << dp[c];
    
    return 0;
}