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\n6 13\n4 8\n3 6\n5 12
Output:
14
Solution in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n, W;
cin >> n >> W;
vector<int> weight(n), value(n);
for(int i=0;i<n;i++){
cin >> weight[i] >> value[i];
}
vector<int> dp(W+1, 0);
for(int i=0;i<n;i++){
for(int w=W; w>=weight[i]; w--){
dp[w] = max(dp[w], dp[w-weight[i]] + value[i]);
}
}
cout << dp[W];
return 0;
}