a330: 主任的背包問題
標籤 : DP 背包
通過比率 : 35人/41人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-03-27 23:30

內容

繼校長之後,主任也鼓勵大家把有價值的東西都帶在身上

所以外堂課的時候進階助教都盡量把東西帶著

很多人看到進階助教背包包去上外堂課,就會叫他順便幫忙拿東西

導致他可能要塞很多一樣的書進書包

所以請幫他塞書包,讓書包裡的內容物價值最大化吧

輸入說明

每個測資點單筆測資

第一行有兩正整數 $n,c$

代表總共有$n$個東西

背包容量為$c$

接下來有$n$行,每行三個整數$v,w,k$

代表一個東西價值$a$、體積$b$、總共有$k$個可以放

輸出說明

輸出一整數代表能達到的最大價值

範例輸入
7 50
66 31 1
232 10 4
49 20 1
54 19 1
426 4 3
589 3 10
10 6 4
範例輸出
7178
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (30%): 1.0s , <1K
公開 測資點#2 (30%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
提示 :

90% $n \leq 10^2 ,c \leq 10^4 ,max(k) \leq 10^2$

10% $n \leq 10^2,c\leq 10^6,max(k) \leq 10^2$

標籤:
DP 背包
出處:
108學年度下學期進階班練習題 [管理者:
fdhs107_KonChin... (konchin)
]


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