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

最近更新 : 2021-01-22 07:27

Content

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

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

Input

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

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

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

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

$1≤a_i≤10^2, 0≤b_i≤10^2$

$a_i$有機會重複

Output

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

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

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

對於 30% 的測資 $b_i ≥ 100, n = 100$

對於 60% 的測資 無限制

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


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