PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 請教 ZeroJudge c824/c835 的01背包問題

看板Prob_Solve (計算數學 Problem Solving)作者 (胖胖貓)時間5年前 (2019/02/27 00:35), 5年前編輯推噓1(1推 0噓 9→)
留言10則, 2人參與, 5年前最新討論串1/1
如題，這兩題的題目敘述和要求都是相同的，但特別之處在於物品的重量和背包負重都是2 的次方項，要求和01背包問題一樣問價值總和最大化。 想問一下解題方向或是想法，自己google了一下沒看到有題解也不知道怎麼下關鍵字和01背 包做區隔，先謝謝各位大大的回覆。 因為輸入的物品數量高達1e6個，而且重量和2的次方項有關，就異想天開想說會不會和 Huffman-Code 的編碼方式有關，所以寫了一個初版本，通過51%測資而已。 以下是我的程式碼：https://www.codepile.net/pile/A71bYyDz -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1551198940.A.FA1.html ※ 編輯: fatcat8127 (36.226.99.91), 02/27/2019 04:20:18 ※ fatcat8127:轉錄至看板 C_and_CPP 02/27 05:14
推
02/27 19:52, 5年前 , 1F
對於重量2^k時，我們把價值最大的兩個合在一起湊出重量2^{
02/27 19:52, 1F
→
02/27 19:52, 5年前 , 2F
k+1}的物品，一直做到重量2^k的剩下一個或零個。如果剩一
02/27 19:52, 2F
→
02/27 19:52, 5年前 , 3F
個我們再考慮加入一個重量2^k價值為0的物品，讓剩的那個也
02/27 19:52, 3F
→
02/27 19:52, 5年前 , 4F
可以合上去，這樣直接看重量2^M中，價值最大的那個物品就
02/27 19:52, 4F
→
02/27 19:52, 5年前 , 5F
好。因為可以證明在每個重量最多加入一個價值為0的東西時
02/27 19:52, 5F
→
02/27 19:52, 5年前 , 6F
，用最優解選完選到一些價值為0的東西並不會影響答案
02/27 19:52, 6F
→
02/27 20:34, 5年前 , 7F
一份有點慢的AC code https://goo.gl/fBCRZC
02/27 20:34, 7F
→
02/28 01:52, 5年前 , 8F
感謝大大的說明和程式碼
02/28 01:52, 8F
→
02/28 03:57, 5年前 , 9F
根據我自己的理解和今天討論區的回覆，解法就是建立B
02/28 03:57, 9F
→
02/28 03:57, 5年前 , 10F
inominal Heap的過程嗎
02/28 03:57, 10F
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1STMhS-X (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1STMhS-X (Prob_Solve)