Problem 10: 0/1 Knapsack Problem
Problem Statement: Given a set of items, each with a weight and a value, determine the maximum value that can be achieved with a given capacity using 0/1 Knapsack Dynamic Programming.
Input
First line contains n and W, number of items and maximum capacity. Each of the next n lines contains two integers: weight and value.
Output
Print the maximum value achievable within the capacity.
Examples
Input:
4 7
6 13
4 8
3 6
5 12
Output:
14
Solution Explanation
Method 1: Use dynamic programming where dp[i][w] represents the maximum value using the first i items with capacity w; optimize by iterating backwards on weight. Method 2: Use a space optimized version that only uses a 1D dp array updated in reverse order for each item.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n, W;
cin >> n >> W;
vector weight(n), value(n);
for(int i=0;i> weight[i] >> value[i];
}
vector dp(W+1, 0);
for(int i=0;i=weight[i]; w--){
dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);
}
}
cout << dp[W];
return 0;
}