c824: 第六題:背包問題 EX
標籤 :
通過比率 : 36% (4 人 / 11 人 ) (非即時)
評分方式:
Tolerant

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

內容

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

輸入說明

輸入第一列為正整數$\color{black}{\space N,M\space}$,表示共有$\color{black}{\space N\space}$個物品,且背包內容物的總重量限制為$\color{black}{\space 2^M\space}$。

接著有$\color{black}{\space N\space}$列,每一列為一個物品,包含兩個非負整數$\color{black}{\space a,b\space}$,表示該物品的重量為$\color{black}{\space 2^a\space}$,而價值為$\color{black}{\space b\space}$。測資點$\color{black}{\space 0\sim 13,a\leq 20\space}$,測資點$\color{black}{\space 14\sim 19,a\leq 10^9\space}$

輸出說明

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

範例輸入
//範例輸入一:
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
範例輸出
//範例輸出一:
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
提示 :

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

評分說明:

測資點$\color{black}{\space 0\space}$:$\color{black}{\space N\leq 10,M\leq 20,b\leq 10^6 \space}$。

測資點$\color{black}{\space 1\sim 2\space}$:$\color{black}{\space N\leq 20,M\leq 10,b\leq 10^9 \space}$。

測資點$\color{black}{\space 3\space}$:$\color{black}{\space N\leq 30,M\leq 5,b\leq 10^6 \space}$。

測資點$\color{black}{\space 4\space}$:$\color{black}{\space N\leq 10^3,M\leq 10,b\leq 10^6 \space}$。

測資點$\color{black}{\space 5\space}$:$\color{black}{\space N\leq 10^3,M\leq 10,b\leq 10^9 \space}$。

測資點$\color{black}{\space 6\sim 7\space}$:$\color{black}{\space N\leq 10^4,M\leq 10,b\leq 10^6 \space}$。

測資點$\color{black}{\space 8\sim 10\space}$:$\color{black}{\space N\leq 10^5,M\leq 20,b\leq 10^6 \space}$。

測資點$\color{black}{\space 10\sim 13\space}$:$\color{black}{\space N\leq 10^6,M\leq 20,b\leq 10^6 \space}$。

測資點$\color{black}{\space 14\sim 15\space}$:$\color{black}{\space N\leq 10^6,M\leq 10^6,b\leq 10^9 \space}$。

測資點$\color{black}{\space 16\sim 19\space}$:$\color{black}{\space N\leq 10^6,M\leq 10^9,b\leq 10^9 \space}$。

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


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