d071: P-6-9. 大賣場免費大搬家
Tags : DP knapsack
Accepted rate : 13人/13人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-11-19 20:18

Content

你抽中了大賣場的周年慶的抽獎活動,在不超過總重量 W 的限制下,你可任意挑選商

品免費帶走。現場一共 n 項商品,每項商品有它的重量與價值,每項商品只可以選或

不選,不可以拆開只拿一部份。請計算可以獲得的最大價值總和。

Input

第一行有兩個正整數 n 與 W

第二行有 n 個正整數,依序代表商品的重量

第三行有 n 個正整數,依序代表對應 n 項商品的價值

 

同一行數字間以空白隔開

n ≤ 100

W 與各商品重量及價值皆不超過 $10^5$

Output

最大價值總和。

Sample Input
// 1
7 10
3 4 2 3 3 6 5
5 5 2 4 4 5 6
// 2
5 14
1 2 3 4 5
3 2 4 4 4
Sample Output
// 1
14
// 2
15
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
DP knapsack
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」