I'm new to c++, just moved from python and gave a try to dynamic programming. Ive written a piece of code for the basic "0-1 knapsack" problem, which is supposed to test my basic understanding of dynamic programming.
I think I got my algorithm right, but for some reason, when i ask the user to enter input for two of the arrays, I get a wrong answer, but when i enter the values of these arrays within the code, I get the correct answer, everytime.
What went wrong/is wrong?
EDIT: dp is a 1001*10001 2d vector filled with -1
My solver function:
int knap(int n, int wt[], int price[], int W){ // n = number of items; size of array, w = wt available in knapsack
// wt stores weight if items, price:price
if(dp[n][W] != -1){
return dp[n][W];
}
else{
// base case
if(n == 0 || W == 0){
return 0;
}
if(wt[n-1] <= W){ // condition for adding item to knapsack (wt of item must be less than space remaining in knapsack)
return dp[n][W] = max((price[n-1] + knap(n-1, wt, price, W - wt[n-1])), knap(n-1, wt, price, W)) ; // max wrt recursion from previous element
}
else{
return dp[n][W] = knap(n-1, wt, price, W);
}
}
}
My main function:
int main(){
int n, W;
cin>>n>>W;
/*int b[n], b[n];
for(int i = 0; i<n; i++)
cin>>a[i];
for(int j = 0; j<n; j++)
cin>>b[j];
*/
int a[] = { 1 ,2 ,10 ,6 ,5 ,1 ,7 ,4 ,10 ,4}, b[] = { 6, 3, 8, 1, 7, 3, 8, 6, 5, 6};
cout<<knap(n, a, b, W);
}
the answer is supposed to be 21, which i get when a[] and b[] have been defined, but when I make the user input a[] and b[] (as written in the commented region of the code) value, I get the wrong answer.
example input test cases with their outputs:
Input:
10 10
1 2 10 6 5 1 7 4 10 4
6 3 8 1 7 3 8 6 5 6
output:
21
Input:
4 10
4 8 5 3
5 12 8 1
Output:
13
