結果
問題 | No.2364 Knapsack Problem |
ユーザー |
![]() |
提出日時 | 2023-06-30 00:19:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,685 ms / 3,000 ms |
コード長 | 926 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 141,824 KB |
最終ジャッジ日時 | 2024-07-07 08:23:48 |
合計ジャッジ時間 | 17,165 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
# N, M が小さいことに注目して bit DP を行う# bit DP でもつべき状態は [今の使ったものの集合][現在の重さ] の価値の最大値# O(2^(N+M) W (N+M)) 間に合うかやや微妙n, m, w = map(int,input().split())a = list(map(int,input().split()))b = list(map(int,input().split()))c = list(map(int,input().split()))d = list(map(int,input().split()))z = n + mdp = [[- 10 ** 18] * (w+1) for i in range(1 << z)]dp[0][0] = 0for i in range(1 << z):for noww in range(w + 1):for j in range(z):if i >> j & 1:if j < n:# buyif noww - a[j] < 0:continuedp[i][noww] = max(dp[i][noww], dp[i^(1<<j)][noww-a[j]] + b[j])else:# use magicif noww + c[j-n] > w:continuedp[i][noww] = max(dp[i][noww], dp[i^(1<<j)][noww+c[j-n]] - d[j-n])ans = 0for i in range(1 << z):for j in range(w + 1):ans = max(ans, dp[i][j])print(ans)