b054: 員生社$禮卷$
標籤 : DP knapsack
通過比率 : 19人/19人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-14 20:39

內容

電電拿到了一張員生社$禮卷$,面額為 $n$ 元

員生社共有 $t$ 件商品

員生社的每件商品都有一個價格 $p_i$ 及重量 $w_i$

求$禮物卷$可買到的最大總重。

輸入說明

第一行 有一個數 $n$, $n ≤ 10^3$

第二行 有一個數 $t$, $ t ≤ 10^3$

接下來有 $t$ 行

每行有兩個數 $p_i$, $w_i$, 皆小於 $10^6$

輸出說明

輸出最大重量

範例輸入 #1
50
5
13 17
23 27
10 37
20 14
50 71
範例輸出 #1
81
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (3%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (3%): 1.0s , <1M
公開 測資點#5 (3%): 1.0s , <1M
公開 測資點#6 (3%): 1.0s , <1M
公開 測資點#7 (3%): 1.0s , <1M
公開 測資點#8 (3%): 1.0s , <1M
公開 測資點#9 (3%): 1.0s , <1M
公開 測資點#10 (3%): 1.0s , <1M
公開 測資點#11 (3%): 1.0s , <1M
公開 測資點#12 (3%): 1.0s , <1M
公開 測資點#13 (3%): 1.0s , <1M
公開 測資點#14 (3%): 1.0s , <1M
公開 測資點#15 (3%): 1.0s , <1M
公開 測資點#16 (3%): 1.0s , <1M
公開 測資點#17 (3%): 1.0s , <1M
公開 測資點#18 (3%): 1.0s , <1M
公開 測資點#19 (3%): 1.0s , <1M
公開 測資點#20 (4%): 1.0s , <1M
公開 測資點#21 (4%): 1.0s , <1M
公開 測資點#22 (4%): 1.0s , <1M
公開 測資點#23 (4%): 1.0s , <1M
公開 測資點#24 (4%): 1.0s , <1M
公開 測資點#25 (4%): 1.0s , <1M
公開 測資點#26 (4%): 1.0s , <1M
公開 測資點#27 (4%): 1.0s , <1M
公開 測資點#28 (4%): 1.0s , <1M
公開 測資點#29 (4%): 1.0s , <1M
提示 :
標籤:
DP knapsack
出處:
臺中一中電腦資訊研習社 [管理者:
Ching367436 (Ching367436)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」