01Knapsack

Fastrail08

May 19th, 2025

435

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.19 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
int solveKnapSack(int index, int profit, int maxW, vector<int> &items, vector<int> &weight, int &max_profit, vector<vector<int> > &memo){
if(index >= items.size()){
max_profit = max(max_profit, profit);
return 0;
}
if(memo[index][maxW] != INT_MIN){
return memo[index][maxW];
}
int itemInc = 0, itemExc = 0;
// item in subset, only if currW + weight[index] <= w
if(maxW - weight[index] >= 0){
itemInc += items[index] + solveKnapSack(index + 1, profit + items[index], maxW - weight[index], items, weight, max_profit, memo);
}
// item not in subset
itemExc = solveKnapSack(index + 1, profit, maxW, items, weight, max_profit, memo);
return memo[index][maxW] = max(itemInc, itemExc);
}
int solveKnapSackDP(vector<int> &items, vector<int> &weight, int &maxW){
vector<vector<int> > dp(items.size(), vector<int> (maxW + 1, -1));
// the first column has wt = 0, so no item can be included, hence profit = 0
for(int i = 0; i < items.size(); i++){
dp[i][0] = 0;
}
for(int j = 1; j <= maxW; j++){
dp[0][j] = j < weight[0] ? 0 : items[0];
}
for(int i = 1; i < items.size(); i++){
for(int j = 1; j <= maxW; j++){
dp[i][j] = j < weight[i] ? dp[i - 1][j] : max(dp[i - 1][j], items[i] + dp[i - 1][j - weight[i]]);
}
}
return dp[items.size() - 1][maxW];
}
int main() {
// your code goes here
int n, maxW;
cin >> n;
vector<int> items(n), weight(n);
for(int i = 0; i < n; i++){
cin >> items[i];
}
for(int i = 0; i < n; i++){
cin >> weight[i];
}
cin >> maxW;
int max_profit = INT_MIN;
vector<vector<int> > memo(n, vector<int>(maxW + 1, INT_MIN));
//memo call (return method)
//cout << max(solveKnapSack(0, 0, maxW, items, weight, max_profit, memo), 0) << '\n';
//(print method)
/*
print max(max_profit, 0), as the min value can be 0 when no items were included
cout << max(max_profit, 0) << '\n';
*/
//dp call
cout << solveKnapSackDP(items, weight, maxW) << '\n';
}

Add Comment

Please, Sign In to add comment