c824. 第六題:背包問題 EX
標籤 :
通過比率 : 27人/99人 ( 27% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-11-05 11:24

內容

  現在請你解決經典的背包問題:桌上有許多物品,已知每個物品的重量與價值,每個物品都可以獨立選擇是否拿取。一開始背包是空的,你希望在背包內容的總重量不超過限制的情形下,選擇一些物品放進背包中,使得背包內的物品價值總和愈高愈好。請問被放進背包中的物品,其價值總和最高為多少呢?

輸入說明

輸入第一列為正整數 N,M ,表示共有 N 個物品,且背包內容物的總重量限制為 2M 

接著有 N 列,每一列為一個物品,包含兩個非負整數 a,b ,表示該物品的重量為 2a ,而價值為 b 。測資點 013,a20 ,測資點 1419,a109 

輸出說明

請輸出一列,其中包含一個正整數,表示被放進背包中的物品,其價值總和最大值。

範例輸入 #1
//範例輸入一:
3 4
1 1
2 2
3 3

//範例輸入二:
5 2
0 1
0 2
0 2
0 3
2 4

//範例輸入三:
7 2
0 5
1 4
1 3
2 1
2 2
2 3
2 4

//範例輸入四:
9 13
11 21
10 12
12 14
14 37
12 14
10 5
11 3
13 17
14 1000
範例輸出 #1
//範例輸出一:
6

//範例輸出二:
8

//範例輸出三:
9

//範例輸出四:
52
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (1%): 1.0s , <1K
不公開 測資點#2 (1%): 1.0s , <1K
不公開 測資點#3 (1%): 1.0s , <1K
不公開 測資點#4 (1%): 1.0s , <1M
不公開 測資點#5 (1%): 1.0s , <1M
不公開 測資點#6 (1%): 1.0s , <1M
不公開 測資點#7 (1%): 1.0s , <1M
不公開 測資點#8 (1%): 1.0s , <1M
不公開 測資點#9 (1%): 1.0s , <1M
不公開 測資點#10 (1%): 1.0s , <1M
不公開 測資點#11 (1%): 1.0s , <10M
不公開 測資點#12 (1%): 1.0s , <10M
不公開 測資點#13 (1%): 1.0s , <10M
不公開 測資點#14 (10%): 1.0s , <50M
不公開 測資點#15 (10%): 1.0s , <50M
不公開 測資點#16 (13%): 1.0s , <50M
不公開 測資點#17 (13%): 1.0s , <50M
不公開 測資點#18 (13%): 1.0s , <50M
不公開 測資點#19 (14%): 1.0s , <50M
不公開 測資點#20 (13%): 1.0s , <50M
提示 :

本題測資為非官方測資,若對測資有疑慮請儘管提出

評分說明:

測資點 0  N10,M20,b106 

測資點 12  N20,M10,b109 

測資點 3  N30,M5,b106 

測資點 4  N103,M10,b106 

測資點 5  N103,M10,b109 

測資點 67  N104,M10,b106 

測資點 810  N105,M20,b106 

測資點 1013  N106,M20,b106 

測資點 1415  N106,M106,b109 

測資點 1619  N106,M109,b109 

標籤:
出處:
107學年度高雄市資訊學科能力競賽複賽 [管理者: baluteshih (波路特石) ]

本題狀況 本題討論 排行

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