Scribd
Upload
28 views1 page

0 - 1 Knapsack With Memoization

The document contains a C++ implementation of the 0/1 Knapsack problem using dynamic programming. It defines a recursive function 'solve' to calculate the maximum profit based on given values and weights, and a main function that initializes the values and weights, then outputs the maximum profit for a specified capacity. The program demonstrates how to optimize the selection of items to maximize profit without exceeding the weight limit.

Uploaded by

Anupam roy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
28 views1 page

0 - 1 Knapsack With Memoization

The document contains a C++ implementation of the 0/1 Knapsack problem using dynamic programming. It defines a recursive function 'solve' to calculate the maximum profit based on given values and weights, and a main function that initializes the values and weights, then outputs the maximum profit for a specified capacity. The program demonstrates how to optimize the selection of items to maximize profit without exceeding the weight limit.

Uploaded by

Anupam roy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

#include <iostream>

#include <vector>
using namespace std;

int solve(vector<int> &values, vector<int> &weights, int index, int capacity, vector<vector<int> >& dp)
{
if(index == 0)
{
if(weights[0] <= capacity)
{
return values[0];
}
else
{
return 0;
}
}

if(dp[index][capacity] != -1)
{
return dp[index][capacity];
}

int include = 0;
if(weights[index] <= capacity)
include = values[index] + solve(values, weights, index - 1, capacity - weights[index], dp);

int exclude = 0 + solve(values, weights, index - 1, capacity, dp);

dp[index][capacity] = max(include, exclude);


return dp[index][capacity];
}

int maxProfit(vector<int> &values, vector<int> &weights, int n, int w)


{
vector<vector<int>> dp(n, vector<int>(w + 1, -1));
return solve(values, weights, n - 1, w, dp);
}

int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int n = values.size();
int W = 50;

cout << "Maximum Profit: " << maxProfit(values, weights, n, W) << endl;
return 0;
}

You might also like