結果
問題 |
No.626 Randomized 01 Knapsack
|
ユーザー |
|
提出日時 | 2017-12-21 23:02:58 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 959 ms / 2,000 ms |
コード長 | 1,406 bytes |
コンパイル時間 | 2,216 ms |
コンパイル使用メモリ | 79,996 KB |
実行使用メモリ | 49,128 KB |
最終ジャッジ日時 | 2024-12-23 11:26:41 |
合計ジャッジ時間 | 14,872 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
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(); } }