test/aoj/DPL_1_H/main.test.bb.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H"
#include <iostream>
#include <vector>
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/Typical/knapsack_branch_and_bound.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
int64_t W;
std::cin >> W;
auto [v, w] = hl::input_tuple_vector<int64_t, int64_t>(N);
auto ans = hl::knapsack_branch_and_bound(N, W, w, v);
std::cout << ans << std::endl;
return 0;
}
#line 1 "test/aoj/DPL_1_H/main.test.bb.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H"
#include <iostream>
#include <vector>
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 2 "Mylib/Typical/knapsack_branch_and_bound.cpp"
#include <algorithm>
#include <numeric>
#line 6 "Mylib/Typical/knapsack_branch_and_bound.cpp"
namespace haar_lib {
template <typename Weight, typename Value>
Value knapsack_branch_and_bound(
int N, Weight cap, const std::vector<Weight> &weight, const std::vector<Value> &value) {
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
std::sort(
ord.begin(), ord.end(),
[&](int i, int j) {
return (double) value[i] / weight[i] > (double) value[j] / weight[j];
});
Value feasible_sol = 0;
auto dfs =
[&](auto &dfs, int k, Weight w, Value v) -> Value {
if (w > cap) return 0;
if (k == N) {
feasible_sol = std::max(feasible_sol, v);
return v;
}
bool is_opt = true;
Value sol = 0;
Weight w_sum = 0;
int p = 0;
for (p = k; p < N; ++p) {
if (w_sum + weight[ord[p]] >= cap - w) {
if (w_sum + weight[ord[p]] == cap - w) {
w_sum += weight[ord[p]];
sol += value[ord[p]];
} else {
is_opt = false;
}
break;
} else {
w_sum += weight[ord[p]];
sol += value[ord[p]];
}
}
if (is_opt) return feasible_sol = std::max(feasible_sol, v + sol);
double d = (double) value[ord[p]] / weight[ord[p]] * (cap - w - w_sum);
if ((double) v + sol + d < feasible_sol) {
return 0;
}
Value ret = 0;
if (w + weight[ord[k]] <= cap) {
ret = std::max(ret, dfs(dfs, k + 1, w + weight[ord[k]], v + value[ord[k]]));
feasible_sol = std::max(feasible_sol, ret);
}
ret = std::max(ret, dfs(dfs, k + 1, w, v));
feasible_sol = std::max(feasible_sol, ret);
return ret;
};
auto ret = dfs(dfs, 0, 0, 0);
return ret;
}
} // namespace haar_lib
#line 7 "test/aoj/DPL_1_H/main.test.bb.cpp"
namespace hl = haar_lib;
int main() {
int N;
std::cin >> N;
int64_t W;
std::cin >> W;
auto [v, w] = hl::input_tuple_vector<int64_t, int64_t>(N);
auto ans = hl::knapsack_branch_and_bound(N, W, w, v);
std::cout << ans << std::endl;
return 0;
}
Back to top page