k622. [棕]0-1背包問題
Tags :
Accepted rate : 40人/69人 ( 58% ) [非即時]
評分方式:
Strictly

最近更新 : 2023-05-24 17:36

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
Hint :
Tags:
出處:
[管理者: 1450840-0@g. ... (肥余好朋友) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
35578 SUNGOD (黑龍炎使.煞氣ㄟSUNGOD) k622
題序有誤
307 2023-06-07 13:23