結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー | 37zigen |
提出日時 | 2017-12-21 23:02:58 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,311 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 4,897 ms |
コンパイル使用メモリ | 75,432 KB |
実行使用メモリ | 63,040 KB |
最終ジャッジ日時 | 2023-08-24 23:52:33 |
合計ジャッジ時間 | 19,324 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 122 ms
55,808 KB |
testcase_01 | AC | 127 ms
56,352 KB |
testcase_02 | AC | 131 ms
55,420 KB |
testcase_03 | AC | 150 ms
56,072 KB |
testcase_04 | AC | 151 ms
55,952 KB |
testcase_05 | AC | 181 ms
56,256 KB |
testcase_06 | AC | 220 ms
57,176 KB |
testcase_07 | AC | 248 ms
58,676 KB |
testcase_08 | AC | 266 ms
58,724 KB |
testcase_09 | AC | 355 ms
60,604 KB |
testcase_10 | AC | 425 ms
60,376 KB |
testcase_11 | AC | 1,006 ms
62,300 KB |
testcase_12 | AC | 1,107 ms
61,028 KB |
testcase_13 | AC | 343 ms
61,276 KB |
testcase_14 | AC | 561 ms
61,452 KB |
testcase_15 | AC | 895 ms
63,040 KB |
testcase_16 | AC | 1,041 ms
60,924 KB |
testcase_17 | AC | 1,135 ms
62,664 KB |
testcase_18 | AC | 966 ms
61,524 KB |
testcase_19 | AC | 1,008 ms
61,164 KB |
testcase_20 | AC | 1,311 ms
61,376 KB |
testcase_21 | AC | 323 ms
61,972 KB |
testcase_22 | AC | 791 ms
62,920 KB |
testcase_23 | AC | 1,118 ms
61,604 KB |
testcase_24 | AC | 283 ms
60,988 KB |
ソースコード
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; class Main { long ans = 0; int N; long W; long[][] a; void dfs(int curPos, long curWeight, long curValue) { ans = Math.max(ans, curValue); if (curPos >= N) return; { long resWeight = W - curWeight; double relaxAns = curValue; for (int i = curPos; i < N && resWeight != 0; ++i) { if (resWeight >= a[i][1]) { relaxAns += a[i][0]; resWeight -= a[i][1]; } else { relaxAns += 1.d * a[i][0] * (1.d * resWeight / a[i][1]); resWeight = 0; } } if (relaxAns <= ans) { return; } } dfs(curPos + 1, curWeight, curValue); if (curWeight + a[curPos][1] <= W) { dfs(curPos + 1, curWeight + a[curPos][1], curValue + a[curPos][0]); } } void run() { Scanner sc = new Scanner(System.in); N = sc.nextInt(); W = sc.nextLong(); a = new long[N][2]; for (int i = 0; i < N; ++i) { a[i][0] = sc.nextLong();//value a[i][1] = sc.nextLong();//weight } Arrays.sort(a, new Comparator<long[]>() { @Override public int compare(long[] arg0, long[] arg1) { return -Double.compare((double) arg0[0] / arg0[1], (double) arg1[0] / arg1[1]); } }); dfs(0, 0, 0); System.out.println(ans); } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } public static void main(String[] args) { new Main().run(); } }