Adding DP to 0/1 knapsack

Question

Here are the two different ways of solving 0/1 knapsack using recursion.

#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);
}

I know how to add dp to the second method (in solve2 function). But I dont know how to add dp to the first method. As the true/false values in vector<bool> sacked will be unique for every call, using dp[capacity][sacked] seems useless as the same dp[capacity][sacked] will never be requested twice

"Am I wrong to conclude that value of vector<bool> sacked will be unique for every recursive function call and consequently DP for solve1 not possible?"

Answer 1

It is possible to memoize results for solve1 as well. For any particular choice of k elements, there are k! possible orders to arrive at that state, so the same answers can be requested multiple times.

The main issue with this method, however, is that the size of a state is quite large and the dynamic programming transition also takes linear time, which tends to be too inefficient to be practical.

Note that the 0/1 knapsack problem can be more simply and elegantly solved with tabulation.

#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();
}