結果

問題 No.527 ナップサック容量問題
ユーザー masa
提出日時 2017-06-10 00:05:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,099 ms / 2,000 ms
コード長 1,227 bytes
コンパイル時間 685 ms
コンパイル使用メモリ 76,328 KB
実行使用メモリ 49,424 KB
最終ジャッジ日時 2024-09-22 20:30:16
合計ジャッジ時間 8,205 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
using namespace std;
int n, v;
vector<int> value, weight;
int calc(int w_max) {
vector<vector<int>> dp(n, vector<int>(w_max + 1001, -1));
dp[0][0] = 0;
dp[0][weight[0]] = value[0];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j <= w_max; j++) {
if (dp[i][j] < 0) {
continue;
}
dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
int nj = j + weight[i+1];
dp[i+1][nj] = max(dp[i+1][nj], dp[i][j] + value[i+1]);
}
}
int ret = 0;
for (int i = 0; i <= w_max; i++) {
ret = max(ret, dp[n - 1][i]);
}
return ret;
}
int main() {
cin >> n;
value.assign(n, 0);
weight.assign(n, 0);
for (int i = 0; i < n; i++) {
cin >> value[i] >> weight[i];
}
cin >> v;
int n_bit = 17;
int maxi = 0;
int mini = (1 << n_bit) - 1;
for (int i = n_bit - 1; i >= 0; i--) {
int tmp1 = maxi + (1 << i);
int tmp2 = mini - (1 << i);
int x = calc(tmp1);
int y = calc(tmp2);
if (x <= v) {
maxi = tmp1;
}
if (y >= v) {
mini = tmp2;
}
}
mini = max(mini, 1);
cout << mini << endl;
if (maxi > 100000) {
cout << "inf" << endl;
} else {
cout << maxi << endl;
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0