-
Notifications
You must be signed in to change notification settings - Fork 240
/
0_1_Knapsack_aniketrochwani.cpp
61 lines (49 loc) · 1.25 KB
/
0_1_Knapsack_aniketrochwani.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
class Solution
{
public:
//Function to return max value that can be put in knapsack of capacity W.
int knapSack(int W, int wt[], int val[], int n)
{
int dp[n+1][W+1];
for(int i=0; i<=W; i++) dp[0][i] = 0;
for(int i=0; i<=n; i++) dp[i][0] = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=W; j++){
if(wt[i-1] <= j){
dp[i][j] = max(val[i-1]+dp[i-1][j-wt[i-1]], dp[i-1][j]);
}else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
};
// { Driver Code Starts.
int main()
{
//taking total testcases
int t;
cin>>t;
while(t--)
{
//reading number of elements and weight
int n, w;
cin>>n>>w;
int val[n];
int wt[n];
//inserting the values
for(int i=0;i<n;i++)
cin>>val[i];
//inserting the weights
for(int i=0;i<n;i++)
cin>>wt[i];
Solution ob;
//calling method knapSack()
cout<<ob.knapSack(w, wt, val, n)<<endl;
}
return 0;
} // } Driver Code Ends