k622.
[棕]0-1背包問題
Content
有n件物品，每件物品都有一個重量和一個價值，我們分別記為W1，W2，…，Wn和C1，C2，…，Cn。現有一個背包，其容量為K，要從n件物品中任取若干件，要求：
(1) 重量之和小於或等於K。
(2) 價格之和最大。
Input
第1行2個整數，表示n和K，1≤n≤20，1≤K≤109。
第2行n個整數，表示每一個物品的重量，1≤Wi≤104。
第3行n個整數，表示每一個物品的價值，1≤Ci≤108。
Output
一行一個整數，代表符合背包容量的最大價值。
Sample Input
#1
8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62
Sample Output
#1
334
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint ：
Tags:
出處:
[管理者：
1450840-0@g....(hi)
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||