現在請你解決經典的背包問題：桌上有許多物品，已知每個物品的重量與價值，每個物品都可以獨立選擇是否拿取。一開始背包是空的，你希望在背包內容的總重量不超過限制的情形下，選擇一些物品放進背包中，使得背包內的物品價值總和愈高愈好。請問被放進背包中的物品，其價值總和最高為多少呢？
輸入第一列為正整數$\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
本題測資為非官方測資，若對測資有疑慮請儘管提出
評分說明：
測資點$\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}$。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||