test/Knapsack01.test.cpp

• View this file on GitHub
• Last update: 2021-03-21 09:59:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B

Depends on

• DP/Knapsack01.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B"
#include "./../DP/Knapsack01.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int N, W;
	cin >> N >> W;
	vector<int> v(N), w(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i] >> w[i];
	}
	cout << Knapsack01(N, W, v, w)[W] << '\n';
}

#line 1 "test/Knapsack01.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_B"
#line 2 "DP/Knapsack01.cpp"
#include <vector>
#include <algorithm>
#include <cassert>

template <class T>
std::vector<T> Knapsack01(int n, int weight_limit, const std::vector<T>& value,
                          const std::vector<int>& weight) {
	assert(n == static_cast<int>(value.size()));
	assert(n == static_cast<int>(weight.size()));
	std::vector<T> dp(weight_limit + 1, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = weight_limit; j >= 0; --j) {
			if (j - weight[i] >= 0) dp[j] = std::max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	return dp;
}
#line 3 "test/Knapsack01.test.cpp"
#include <iostream>
#line 5 "test/Knapsack01.test.cpp"
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int N, W;
	cin >> N >> W;
	vector<int> v(N), w(N);
	for (int i = 0; i < N; ++i) {
		cin >> v[i] >> w[i];
	}
	cout << Knapsack01(N, W, v, w)[W] << '\n';
}

Back to top page