b216. 背包問題 (1) - 旦旦解題農場

內容

你有 $n$ 件物品和一個容量為 $c$ 的背包。每件物品有一個重量 $w_i$ 和一個價值 $v_i$ 。

你只能選擇每件物品放或不放(即最多只能放一次)，求在不超過背包容量的前提下，可以取得的最大總價值是多少？

輸入說明

第一列輸入兩數 $n , c$ 代表物品數量和背包容量。

接下來輸入 $n$ 行 $w_i , v_i$ ，代表第 $i$ 件物品的重量和價值。

輸出說明

輸出可放入的最大總價值。

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <1M
公開測資點#5 (10%): 1.0s , <1M
公開測資點#6 (10%): 1.0s , <1M
公開測資點#7 (10%): 1.0s , <1M
公開測資點#8 (10%): 1.0s , <1M
公開測資點#9 (10%): 1.0s , <1M

提示：

$1 \leq n \leq 10^{3} \; , \; 1 \leq c \leq 10^{5} \; , \; 1 \leq w_i , v_i \leq 10^{5}$

題解。

標籤:

DP 背包

出處:

[管理者：

Pote_Liu (13th 初階助教)

]

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