0/1背包算法

2025年11月26日 235 字大概 1 分钟

0/1背包是我在做P2392时遇到的。
概念是给你一堆物品，每个物品有容量，让你最大化利用一个背包空间。
这道题的背包代码如下

int solve(int n, int* time_arr) {
    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += time_arr[i];
    }
    
    int half = sum / 2;
    
    // 初始化dp数组，每次都要清空哦
    memset(dp, 0, sizeof(dp));
    
    // 0/1 背包模板
    // dp[j] 表示容量为 j 时能装的最大时间
    for(int i = 0; i < n; i++) {
        for(int j = half; j >= time_arr[i]; j--) {
            dp[j] = max(dp[j], dp[j - time_arr[i]] + time_arr[i]);
        }
    }
    
    // dp[half] 是其中一个大脑最接近一半的时间
    // 另一个大脑就是 sum - dp[half]
    // 因为 sum - dp[half] >= dp[half]，所以返回较大值
    return sum - dp[half]; 
}

其中time_arr是时间序列。
注意一定要逆向循环，如果正向循环则是无限背包。
记住状态转移方程：

1	`dp[j] = max(dp[j], dp[j - t] + t);`