VvyLw's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/knapsack3.test.cpp
- View this file on GitHub
- Last update: 2024-03-27 23:05:37+09:00
- Problem: https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_I
Depends on
Code
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_I"
#include <iostream>
#include "C++/other/dp.hpp"
int main() {
int n;
int64_t wg;
std::cin >> n >> wg;
std::vector<int> v(n);
std::vector<int64_t> w(n), m(n);
for(int i = 0; i < n; ++i) {
std::cin >> v[i] >> w[i] >> m[i];
}
std::cout << knapsack_sup_w(w, v, m, wg) << '\n';
}#line 1 "test/knapsack3.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_I"
#include <iostream>
#line 2 "C++/other/dp.hpp"
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
#include <iterator>
#include <limits>
#include <numeric>
template <class T> T knapsack01_v(const std::vector<int> &a, const std::vector<T> &v, const int w) {
const int n = a.size();
std::vector dp(w + 1, std::numeric_limits<T>::min());
dp[0] = 0;
for(int i = 0; i < n; i++) {
for(int j = w; j >= a[i]; j--) {
if(dp[j - a[i]] != std::numeric_limits<T>::min()) {
if(dp[j - a[i]] + v[i] > dp[j]) {
dp[j] = dp[j - a[i]] + v[i];
}
}
}
}
return *std::ranges::max_element(dp);
}
/**
* @see https://ei1333.github.io/library/dp/knapsack-01.hpp
*/
template <class T> int knapsack01_w(const std::vector<T> &a, const std::vector<int> &v, const T &w) {
const int n = a.size();
const int s = std::accumulate(v.begin(), v.end(), 0);
std::vector dp(s + 1, w + 1);
dp[0] = 0;
for(int i = 0; i < n; i++) {
for(int j = s; j >= v[i]; j--) {
dp[j] = std::min(dp[j], dp[j - v[i]] + a[i]);
}
}
int res = 0;
for(int i = 0; i <= s; i++) {
if(dp[i] <= w) {
res = i;
}
}
return res;
}
/**
* @see https://ei1333.github.io/library/dp/knapsack-01-2.hpp
*/
template <class T> std::vector<T> knapsack_sup_v(const std::vector<int> &a, const std::vector<T> &v, const std::vector<int> &m, const int w, const bool less = false) {
const int n = a.size();
std::vector<T> dp(w + 1, std::numeric_limits<T>::min()), deqv(w + 1);
dp[0] = 0;
std::vector<int> deq(w + 1);
for(int i = 0; i < n; ++i) {
if(a[i] == 0) {
for(int j = 0; j <= w; ++j) {
if(dp[j] != std::numeric_limits<T>::min() && (less ? dp[j] + v[i] * m[i] < dp[j] : dp[j] + v[i] * m[i] > dp[j])) {
dp[j] = dp[j] + v[i] * m[i];
}
}
} else {
for(int k = 0; k < a[i]; ++k) {
int s = 0, t = 0;
for(int j = 0; a[i] * j + k <= w; ++j) {
if(dp[a[i] * j + k] != std::numeric_limits<T>::min()) {
const T val = dp[a[i] * j + k] - j * v[i];
while(s < t && (less ? val < deqv[t - 1] : val > deqv[t - 1])) {
t--;
}
deq[t] = j;
deqv[t++] = val;
}
if(s < t) {
dp[j * a[i] + k] = deqv[s] + j * v[i];
if(deq[s] == j - m[i]) {
s++;
}
}
}
}
}
}
return dp;
}
/**
* @see https://ei1333.github.io/library/dp/knapsack-limitations.hpp
*/
template <class T> T knapsack_sup_w(const std::vector<T> &a, const std::vector<int> &v, const std::vector<T> &m, const T &w) {
const int n = a.size();
const int max = *std::ranges::max_element(v);
if(max == 0) {
return 0;
}
std::vector<int> ma(n);
std::vector<T> mb(n);
for(int i = 0; i < n; i++) {
ma[i] = std::min<int>(m[i], max - 1);
mb[i] = m[i] - ma[i];
}
int sum = 0;
for(int i = 0; i < n; ++i) {
sum += ma[i] * v[i];
}
std::vector dp = knapsack_sup_v(v, a, ma, sum, true);
std::vector<int> id(n);
std::iota(id.begin(), id.end(), 0);
std::stable_sort(id.begin(), id.end(), [&](const int i, const int j) -> bool { return v[i] * a[j] > v[j] * a[i]; });
T res = T{};
for(size_t i = 0; i < dp.size(); ++i) {
if(dp[i] > w || dp[i] == std::numeric_limits<T>::min()) {
continue;
}
T rest = w - dp[i], cost = i;
for(const int j: id) {
const T get = std::min(mb[j], rest / a[j]);
if(get <= 0) {
continue;
}
cost += get * v[j];
rest -= get * a[j];
}
res = std::max(res, cost);
}
return res;
}
/**
* @see https://ei1333.github.io/library/dp/knapsack-limitations-2.hpp
*/
template <class T> T knapsack(const std::vector<int> &a, const std::vector<T> &v, const int w) {
const int n = a.size();
std::vector dp(w + 1, std::numeric_limits<T>::min());
dp[0] = 0;
for(int i = 0; i < n; i++) {
for(int j = a[i]; j <= w; j++) {
if(dp[j - a[i]] != std::numeric_limits<T>::min()) {
if(dp[j - a[i]] + v[i] > dp[j]) {
dp[j] = dp[j - a[i]] + v[i];
}
}
}
}
return *std::ranges::max_element(dp);
}
/**
* @see https://ei1333.github.io/library/dp/knapsack.hpp
*/
template <class T> inline long long max_rectangle(std::vector<T> h) {
h.resize(h.size() + 1);
std::stack<size_t> sk;
std::vector<int> l(h.size());
long long res = 0;
for(size_t i = 0; i < h.size(); i++) {
while(!sk.empty() && h[sk.top()] >= h[i]) {
res = std::max(res, (long long) (i - l[sk.top()] - 1) * h[sk.top()]);
sk.pop();
}
l[i] = sk.empty() ? -1 : sk.top();
sk.emplace(i);
}
return res;
}
/**
* @see https://ei1333.github.io/library/dp/largest-rectangle.hpp
*/
inline int lcs(const std::string &s, const std::string &t) {
const int n = s.size();
std::vector<int> dp(n + 1), ndp(n + 1);
for(size_t i = 0; i < t.size(); ++i) {
for(int j = 0; j < n; ++j) {
if(s[j] == t[i]) {
ndp[j + 1] = dp[j] + 1;
} else {
ndp[j + 1] = std::max(ndp[j], dp[j + 1]);
}
}
dp.swap(ndp);
}
return dp[n];
}
/**
* @see https://maku.blog/p/a3jyhwd/
*/
template <class T> inline std::vector<int> lis(const std::vector<T> &v) {
const int n = v.size();
std::vector<std::pair<T, int>> dp;
std::vector<int> p(n, -1), res;
for(int i = 0; i < n; ++i) {
const auto it = std::ranges::lower_bound(dp, std::make_pair(v[i], -i));
if(it != dp.begin()) {
p[i] = -prev(it) -> second;
}
if(it == dp.end()) {
dp.emplace_back(std::make_pair(v[i], -i));
} else {
*it = std::make_pair(v[i], -i);
}
}
for(int i = -dp.back().second; i != -1; i = p[i]) {
res.emplace_back(i);
}
std::ranges::reverse(res);
return res;
}
/**
* @see https://nyaannyaan.github.io/library/dp/longest-increasing-sequence.hpp
*/
/**
* @brief DP(Knapsack, LCS, LIS, 最大長方形, coin)
*/
#line 4 "test/knapsack3.test.cpp"
int main() {
int n;
int64_t wg;
std::cin >> n >> wg;
std::vector<int> v(n);
std::vector<int64_t> w(n), m(n);
for(int i = 0; i < n; ++i) {
std::cin >> v[i] >> w[i] >> m[i];
}
std::cout << knapsack_sup_w(w, v, m, wg) << '\n';
}