将DP添加到0/1背包

Question

以下是使用递归求解 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);
}

我知道如何将 dp 添加到第二种方法（在

solve2

函数中）。但我不知道如何将 dp 添加到第一种方法中。由于

vector<bool> sacked

中的真/假值对于每个调用都是唯一的，因此使用 dp[capacity][sacked] 似乎毫无用处，因为同一个 dp[capacity][sacked] 永远不会被请求两次

“我是否错误地得出这样的结论：

vector<bool> sacked

的值对于每个递归函数调用都是唯一的，因此

solve1

的 DP 是不可能的？”

Answer 1

也可以记住

solve1

的结果。对于

k

元素的任何特定选择，都有

k!

可能的顺序到达该状态，因此可以多次请求相同的答案。

然而，这种方法的主要问题是状态的大小相当大，并且动态编程转换也需要线性时间，这往往效率太低而不实用。

注意，0/1背包问题可以通过制表更加简单优雅地解决。

#include <span>
#include <vector>
#include <algorithm>
long long solve(int capacity, std::span<int> weights, std::span<int> values) {
    std::vector<long long> bestVal(capacity + 1);
    for (decltype(values.size()) i = 0; i < values.size(); ++i)
        for (int j = capacity; j >= weights[i]; --j)
            bestVal[j] = std::max(bestVal[j], bestVal[j - weights[i]] + values[i]);
    return bestVal.back();
}