Submission #1868357
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
#define INF (ll)1e18
#define SIZE 210
ll n, W;
ll best_feasible = -INF;
vector<P> ab;
vll v, w;
// [0, i)がb[0, i)のように確定していて、その後が不確定である時、線形緩和問題を解く
// 返り値(double, bool) = (緩和問題の最適解, その最適解が元問題の制約を厳密に満たすか)
pair<double, bool> solveRelaxationProblem(ll i, bitset<SIZE>& b) {
double ans = 0;
double w_now = W;
rep(j, i) ans += b[j] * v[j], w_now -= b[j] * w[j];
bool faf = 1;
repi(j, i, n) {
double tmp = min<double>(w_now, w[j]);
faf &= (tmp == 0 || tmp == w[j]);
w_now -= tmp;
ans += tmp * (v[j] * 1.0 / w[j]);
}
return make_pair(ans, faf);
}
// [0, i)がb[0, i)のように確定していてその後が不確定である時、線形緩和問題を解く
// (負荷情報として、確定しているところの価値総和がv_now, 重さ総和w_nowを持っておく)
//
// 返り値double = 最適解
ll dfs(ll i, bitset<SIZE>& b, ll v_now, ll w_now) {
// string s = b.to_string(); reverse(begin(s), end(s)); cout << s << endl;
if (i == n) { best_feasible = max<ll>(best_feasible, v_now); return v_now; }
auto relax_p = solveRelaxationProblem(i, b);
double relax = relax_p.first;
double satisfiability = relax_p.second;
if (satisfiability) { best_feasible = max<ll>(best_feasible, relax); return relax; } // 緩和問題の解を与える選び方が元問題の制約を満たしているので、それが最適でもある
if (relax < best_feasible) { return -INF; } // 緩和問題の解が、今までの最善許容解に達さないので、探索しても無駄
ll tmp = -INF;
// 解がありそうな方を先に分岐するのが極めて重要!今回、0->1の順番で分岐するとTLEする。
// 1を分岐
if (w_now+w[i]<=W) {
b[i] = 1;
chmax(tmp, dfs(i+1, b, v_now+v[i], w_now+w[i]));
b[i] = 0;
chmax(best_feasible, tmp);
}
// 0を分岐
chmax(tmp, dfs(i+1, b, v_now, w_now));
chmax(best_feasible, tmp);
return tmp;
}
int main(void) {
cin >> n >> W;
ab.resize(n); rep(i, n) cin >> ab[i].first >> ab[i].second;
sort(ab.begin(), ab.end(), [&](P l, P r) { return l.first*r.second>r.first*l.second; });
v = vll(n), w = vll(n);
rep(i, n) {
v[i] = ab[i].first;
w[i] = ab[i].second;
}
bitset<SIZE> b;
cout << dfs(0, b, 0, 0) << endl;;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - ナップサック問題 |
User |
hamko |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3056 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
34 / 34 |
33 / 33 |
33 / 33 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask1 |
subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask2 |
subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt |
Subtask3 |
subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask00_sample_1.txt |
AC |
1 ms |
256 KB |
subtask00_sample_2.txt |
AC |
1 ms |
256 KB |
subtask00_sample_3.txt |
AC |
1 ms |
256 KB |
subtask00_sample_4.txt |
AC |
1 ms |
256 KB |
subtask01_0.txt |
AC |
1 ms |
256 KB |
subtask01_1.txt |
AC |
1 ms |
256 KB |
subtask01_10.txt |
AC |
1 ms |
256 KB |
subtask01_11.txt |
AC |
1 ms |
256 KB |
subtask01_12.txt |
AC |
1 ms |
256 KB |
subtask01_13.txt |
AC |
1 ms |
256 KB |
subtask01_14.txt |
AC |
1 ms |
256 KB |
subtask01_2.txt |
AC |
1 ms |
256 KB |
subtask01_3.txt |
AC |
1 ms |
256 KB |
subtask01_4.txt |
AC |
1 ms |
256 KB |
subtask01_5.txt |
AC |
1 ms |
256 KB |
subtask01_6.txt |
AC |
1 ms |
256 KB |
subtask01_7.txt |
AC |
1 ms |
256 KB |
subtask01_8.txt |
AC |
1 ms |
256 KB |
subtask01_9.txt |
AC |
1 ms |
256 KB |
subtask02_0.txt |
AC |
2 ms |
256 KB |
subtask02_1.txt |
AC |
2 ms |
256 KB |
subtask02_10.txt |
AC |
2 ms |
256 KB |
subtask02_11.txt |
AC |
2 ms |
256 KB |
subtask02_12.txt |
AC |
2 ms |
256 KB |
subtask02_13.txt |
AC |
1 ms |
256 KB |
subtask02_14.txt |
AC |
2 ms |
256 KB |
subtask02_2.txt |
AC |
2 ms |
256 KB |
subtask02_3.txt |
AC |
3 ms |
256 KB |
subtask02_4.txt |
AC |
2 ms |
256 KB |
subtask02_5.txt |
AC |
2 ms |
256 KB |
subtask02_6.txt |
AC |
2 ms |
256 KB |
subtask02_7.txt |
AC |
2 ms |
256 KB |
subtask02_8.txt |
AC |
2 ms |
256 KB |
subtask02_9.txt |
AC |
2 ms |
256 KB |
subtask03_0.txt |
AC |
2 ms |
256 KB |
subtask03_1.txt |
AC |
2 ms |
256 KB |
subtask03_10.txt |
AC |
2 ms |
256 KB |
subtask03_11.txt |
AC |
1 ms |
256 KB |
subtask03_2.txt |
AC |
2 ms |
256 KB |
subtask03_3.txt |
AC |
2 ms |
256 KB |
subtask03_4.txt |
AC |
3 ms |
256 KB |
subtask03_5.txt |
AC |
2 ms |
256 KB |
subtask03_6.txt |
AC |
2 ms |
256 KB |
subtask03_7.txt |
AC |
2 ms |
256 KB |
subtask03_8.txt |
AC |
2 ms |
256 KB |
subtask03_9.txt |
AC |
2 ms |
256 KB |