c039: VIII. 點點的$零錢$
Tags : DP knapsack
Accepted rate : 4人/7人 ( 57% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-17 17:58

Content

點點有很多零錢,重量很重

他要買一個東西,期望花最多零錢個數,以減輕重量。

Input

第一行有 $n$, $p$, 代表他有幾種零錢及商品價格

的二行有 $n$ 個數 $a_i$ 代表零錢面額

第三行有 $n$ 個數 $b_i$ 代表零錢個數

$1≤n≤10^3, 0<p≤10^5$

$1≤a_i≤10^3, 0≤b_i≤10^5$

$a_i$ 有機會重複

Output

輸出最大零錢花費個數, 如果需找零,則輸出-1

Sample Input #1
5 21
2 7 3 5 9
3 4 5 6 7
Sample Output #1
8
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 3.0s , <1M
公開 測資點#4 (5%): 3.0s , <1M
公開 測資點#5 (5%): 3.0s , <1M
公開 測資點#6 (5%): 3.0s , <1M
公開 測資點#7 (5%): 5.0s , <1M
公開 測資點#8 (5%): 5.0s , <1M
公開 測資點#9 (5%): 5.0s , <1M
公開 測資點#10 (5%): 5.0s , <1M
公開 測資點#11 (5%): 5.0s , <1M
公開 測資點#12 (5%): 5.0s , <1M
公開 測資點#13 (5%): 5.0s , <1M
公開 測資點#14 (5%): 5.0s , <1M
公開 測資點#15 (5%): 5.0s , <1K
公開 測資點#16 (5%): 5.0s , <1M
公開 測資點#17 (5%): 10.0s , <1M
公開 測資點#18 (5%): 10.0s , <1M
公開 測資點#19 (5%): 10.0s , <1M
Hint :

對於 10% 的測資 $n=1$

對於 90% 的測資 無限制

Tags:
DP knapsack
出處:
臺中一中電腦資訊研習社 [管理者:
Ching367436 (Ching367436)
]


ID User Problem Subject Hit Post Date
52
Ching367436 (Ching367436)
c039
題解
298 2021-01-28 10:33