test/Knapsack.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_C

Depends on

• DP/Knapsack.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_C"
#include "./../DP/Knapsack.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 << Knapsack(N, W, v, w)[W] << '\n';
}

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

template <class T>
std::vector<T> Knapsack(int n, int wight_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(wight_limit + 1, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= wight_limit - weight[i]; ++j) {
			dp[j + weight[i]] = std::max(dp[j + weight[i]], dp[j] + value[i]);
		}
	}
	return dp;
}
#line 3 "test/Knapsack.test.cpp"
#include <iostream>
#line 5 "test/Knapsack.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 << Knapsack(N, W, v, w)[W] << '\n';
}

Back to top page