0/1 KnapSack

Resources:

 GeeksForGeeks

HackerEarth 

Codeforces 

CF blog 

 

Code:

	///https://atcoder.jp/contests/dp/tasks/dp_d
	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	ll wt[12345], val[12345];
	ll Knapsack(ll w, ll wt[], ll val[], ll n)
	{
	ll k[n + 1][w + 1];
	for (int i = 0; i <= n; i++)
	{
	for (int j = 0; j <= w; j++)
	{
	if (i == 0 || j == 0)k[i][j] = 0;
	else if (wt[i - 1] <= j)
	k[i][j] = max(val[i - 1] + k[i - 1][j - wt[i - 1]], k[i - 1][j]);
	else k[i][j] = k[i - 1][j];
	}
	}
	return k[n][w];
	}
	int main()
	{
	ll n, W;
	memset(val, 0, sizeof(val));
	memset(wt, 0, sizeof(wt));
	scanf("%lld %lld", &n, &W);
	for (int i = 0; i < n; i++)
	{
	scanf("%lld%lld", &wt[i], &val[i]);
	}
	ll ans = 0;
	ans += Knapsack(W, wt, val, n);
	printf("%lld\n", ans);
	return 0;
	}

view raw KnapSackBottomUp.cpp hosted with ❤ by GitHub

 

Code: (When Knapsack size is large)

 

 

 

	///https://atcoder.jp/contests/dp/tasks/dp_e
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	#define MSET(x) memset(x, 0x3f, sizeof(x));
	const int Max = 1001 * 105;
	ll n, W, value, weight, ans;
	//int knapSack[Max];
	int main()
	{
	FASTIO
	/*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	cin >> n >> W;
	vector<ll>knapSack(Max, INT_MAX);
	knapSack[0] = 0;
	ans = 0;
	for (int i = 1; i <= n; i++) {
	cin >> weight >> value;
	for (int j = ans; j >= 0; j--) {
	//cerr << knapSack[j]<< " + "<< weight <<" <= "<<W<< " && "<< knapSack[j+value] << " > "<<knapSack[j] + weight;
	if (knapSack[j] + weight <= W && knapSack[j + value] > knapSack[j] + weight) {
	// cerr << knapSack[j]<< " + "<< weight <<" <= "<<W<< " && "<< knapSack[j+value] << " > "<<knapSack[j] + weight;
	knapSack[j + value] = knapSack[j] + weight;
	ans = max(ans, j + value);
	//cerr <<"--> "<< ans << endl;
	}
	//cerr <<"--> "<< ans << endl;
	}
	}
	cout << ans << endl;
	return 0;
	}

view raw LargeKnapSack.cpp hosted with ❤ by GitHub

ProblemList:

B. Checkout Assistant 

UVA 

A2Online Judge 

 

Share: