Solution for Knapsack 2 in C++


May 27, 2020 0.333581 seconds C++
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef pair<int, int> pii; 
//typedef pair<LL, LL> pll; 
typedef pair<string, string> pss; 
//typedef vector<int> vi; 
//typedef vector<vi> vvi; 
typedef vector<pii> vii; 
//typedef vector<LL> vl; 
//typedef vector<vl> vvl;
typedef queue<int> qi;
typedef queue<char> qc;
typedef stack<int> si;
typedef stack<char> sc;
#define F first
#define S second
#define PB push_back


const int MAXV = 1e5 + 10;
const int MAXN = 1e3 + 10;
const ll INF = 1e13;

ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];

int main(){

	cin >> N >> W;
	for(int i = 1;i<=N;i++){
		cin >> wi[i] >> vi[i];
		V += vi[i];
	}

	for(int i = 1;i<=V;i++) dp[i] = INF;
	dp[0] = 0;
	
	for(int item = 1;item<=N;item++){
		int w = wi[item], v = vi[item];
		for(int i = V;i>=v;i--){
			dp[i] = min(dp[i],dp[i - v] + w);
		}
	}

	for(int i = V;i>=0;i--){
		if(dp[i] <= W){
			cout << i << endl;
			break;
		}
	}

	return 0;

}

Editorial


No editorial for this problem. :(

Original Problem


You can view the original page for this problem on the DMOJ.