Recursive solution in c++ using 2dArray


#1
#define LIMIT 10000001
typedef long long int ll;
ll dp[1001][1001];
ll knapSack(const vector<int> &A, const vector<int> &B, const vector<int> &C, int n, int cap) {
if (cap == 0) {
    return 0;
}

if (n >= B.size() || cap < 0) {
    return LIMIT;
}

if (dp[n][cap] != LIMIT) {
    return dp[n][cap];
}

ll ans = INT_MAX;
ans = min(C[n] + knapSack(A, B, C, n, cap - B[n]), ans);
ans = min(knapSack(A, B, C, n+1, cap), ans);

dp[n][cap] = ans;
return ans;
}

int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
int n = B.size();
int maxCap = 0, total = 0;
for (int i = 0; i < A.size(); i++) {
    maxCap = max(A[i], maxCap);
    total += A[i];
}
for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= maxCap; j++) {
        dp[i][j] = LIMIT;
    }
}
ll ans = 0;
for (int i =0; i < A.size(); i++) {
    
    ans += knapSack(A, B, C, 0, A[i]);
}

return ans;
}

#2
    if (cap == 0) {
        return 0;
    }

    if (n >= B.size() || cap < 0) {
        return LIMIT;

This gives the correct answer but why can’t we simply write:

    if (n >= B.size() || cap <= 0) {
        return LIMIT;

P.S This gives wrong answer but I am not getting this. Please help.