Skip to content

Instantly share code, notes, and snippets.

@zarc1411
Last active October 12, 2020 12:20
Show Gist options
  • Save zarc1411/92250d5d4c94d09e3ffa19b180f1193c to your computer and use it in GitHub Desktop.
Save zarc1411/92250d5d4c94d09e3ffa19b180f1193c to your computer and use it in GitHub Desktop.
knapsack 0/1
#include<bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int knapsack(int val[] , int wt[] , int n , int w){
if(dp[n][w]!=-1){
return dp[n][w];
}
if(n==0 || w == 0){
return 0;
}
if(wt[n-1]<=w){
return dp[n][w] = max (val[n-1]+knapsack(val , wt , n-1 , w-wt[n-1]) , knapsack(val , wt , n-1,w));
}
else{
return dp[n][w] = knapsack(val , wt , n-1 , w);
}
}
int main() {
memset(dp , -1 , sizeof(dp));
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int w;
cin>>w;
int val[n];
int wt[n];
for(int i = 0 ; i<n ; i++){
cin>>val[i];
}
for(int i = 0 ; i<n ; i++){
cin>>wt[i];
}
int ans = knapsack(val , wt , n , w);
cout<<ans<<"\n";
}
return 0;
}
=============================================================================================================================
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int w;
cin>>w;
int dp[n+1][w+1];
int val[n];
for(int i = 0 ; i<n ; i++){
cin>>val[i];
}
int wt[n];
for(int i = 0 ; i<n ; i++){
cin>>wt[i];
}
for(int i = 0 ; i<=n ; i++){
for(int j = 0 ; j<=w ; j++){
if(i==0 || j ==0)
dp[i][j] = 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];
}
}
}
cout<< dp[n][w]<<'\n';
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment