为0-1背包问题的第一种递归解法添加DP的疑问

问题描述 #

以下是两种递归解决0-1背包问题的代码：

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vb vector<bool>

long long solve1(int capacity, vi &weight, vi &value, vb &sacked){
    long long ans = 0;
    int n = weight.size();
    for(int i=0; i<n; i++){
        if(sacked[i] || weight[i]>capacity) continue;
        sacked[i]=true;
        ans = max(ans, value[i] + solve1(capacity-weight[i], weight, value, sacked));
        sacked[i]=false;
    }
    return ans;
}

long long solve2(int capacity, vi &weight, vi &value, int idx){
    if(idx==-1) return 0;
    long long ans = solve2(capacity, weight, value, idx-1);
    if(weight[idx]<=capacity) ans = max(ans, value[idx] + solve2(capacity-weight[idx], weight, value, idx-1));
    return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, c;
    cin>>n>>c;
    vi w(n), v(n);
    for(int i=0; i<n; i++) cin>>w[i]>>v[i];
    vb sacked(n, false);
    cout<<solve1(c, w, v, sacked)<<'\n';
    cout<<solve2(c, w, v, n-1);
}

我知道如何为第二种方法（solve2函数）添加动态规划（DP），但不清楚如何为第一种方法（solve1函数）添加DP。由于每次递归调用中vector<bool> sacked的真假值都是唯一的，使用dp[capacity][sacked]似乎毫无意义，因为相同的dp[capacity][sacked]状态不会被重复请求。

请问我的结论是否错误？即vector<bool> sacked的值在每次递归调用中都是唯一的，因此无法为solve1添加DP？

解答 #

你的结论存在偏差，solve1并非完全无法添加DP优化，但原写法的状态设计确实存在极大冗余，导致重复状态难以复用。

核心问题：sacked状态的冗余性 #

你认为sacked的每个状态都是唯一的，这是误解——递归过程中，不同的选择路径完全可能最终到达相同剩余容量+相同物品选取集合的状态，只是路径顺序不同。比如先选物品0再选物品1，和先选物品1再选物品0，最终sacked状态一致、剩余容量也一致，但原写法会重复计算两次该状态的最优值。

真正的问题是vector<bool>作为状态键值极不实用：它无法直接作为DP数组的索引，且存储、哈希成本极高，这才是原写法难以做DP优化的核心原因，而非状态完全不重复。

如何给solve1改造DP优化 #

要给solve1加DP，需先修改状态表示方式，将sacked转化为更紧凑、可索引的形式：

• 用位掩码代替vector：若物品数量n≤64，可用unsigned long long存储选取状态（每一位代表对应物品是否被选），状态可表示为dp[capacity][mask]。但这种方式空间复杂度为O(C*2^n)，当n超过20时会因空间爆炸不可行。
• 引入顺序约束调整递归逻辑：solve1本质是无顺序枚举可选物品，和solve2按顺序处理物品等价。可以给solve1添加start参数，规定只从start索引之后的物品中选择，状态简化为dp[capacity][start]——这和solve2的DP状态dp[idx][capacity]完全一致，自然能使用常规背包DP优化。

改造后的示例代码：

long long solve1_dp(int capacity, vi &weight, vi &value, int start, vector<vector<long long>> &dp){
    if(start == weight.size()) return 0;
    if(dp[capacity][start] != -1) return dp[capacity][start];
    // 不选当前start位置的物品
    long long ans = solve1_dp(capacity, weight, value, start+1, dp);
    // 选当前start位置的物品（如果容量足够）
    if(weight[start] <= capacity){
        ans = max(ans, value[start] + solve1_dp(capacity - weight[start], weight, value, start+1, dp));
    }
    return dp[capacity][start] = ans;
}

总结 #

原solve1写法因用vector<bool>表示选取状态，导致状态存储和复用成本极高，看似无法加DP，但本质是状态设计问题。通过调整状态表示方式或引入顺序约束，完全可以给solve1加上有效的DP优化。你的结论错误在于认为sacked状态完全唯一，实际上存在大量重复状态，只是原状态形式不适合复用。

内容的提问来源于stack exchange，提问作者heman