回『競賽題庫』
c824. 第六題：背包問題 EX
標籤 :
通過比率 : 27人/100人 ( 27% ) [非即時]
評分方式：
Tolerant

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

內容

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

輸入說明

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

接著有 N 列，每一列為一個物品，包含兩個非負整數 a,b ，表示該物品的重量為 2a ，而價值為 b 。測資點 0∼13,a≤20 ，測資點 14∼19,a≤109 

輸出說明

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

範例輸入 #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 ： N≤10,M≤20,b≤106 。

測資點 1∼2 ： N≤20,M≤10,b≤109 。

測資點 3 ： N≤30,M≤5,b≤106 。

測資點 4 ： N≤103,M≤10,b≤106 。

測資點 5 ： N≤103,M≤10,b≤109 。

測資點 6∼7 ： N≤104,M≤10,b≤106 。

測資點 8∼10 ： N≤105,M≤20,b≤106 。

測資點 10∼13 ： N≤106,M≤20,b≤106 。

測資點 14∼15 ： N≤106,M≤106,b≤109 。

測資點 16∼19 ： N≤106,M≤109,b≤109 。

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

本題狀況 本題討論 排行

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