頁:
[1]
2
請各位大大幫我解一下這一題
本帖最後由 aa1379aa 於 2011-6-24 08:28 PM 編輯<這是我的程式碼:pastie.org/2115788不知道這樣寫有沒有問題>問題描述 ：兩名小偷，一同犯案偷了一堆物品，準備進行分贓。每件物品均有其標價且不可分割，標價均為整數。請將這些物品分成兩堆，使其總價值差距最小。輸入說明 ：程式的輸入包含兩行數字，第一行包含一個正整數k，1 ≤ k ≤ 20，代表共有k件物品，其價值分別為n1, n2, ..., nk，1 ≤ ni ≤ 1000，而此k個正整數間以空格隔開。輸出說明 ：輸出所有可能分堆情形中，兩堆價值差距的最小值。範例 ：...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 與其看程式碼，可不先簡略敘述你對於此問題提出演算法之粗略概念？ 你的作法不太對
如果有6個東西分別是1 1 1 1 1 5
分成(1 1 1 1 1)和(5)加值差距是0
不一定兩堆數量要一樣
如果純枚舉的話複雜度是o(k*2^k)<=o(20*1048576)差強人意
這題其實可以轉化成背包問題
背包容量是所有權值和的一半
直接拿範測模擬:
容量=(5+13+21+30+35)/2=52
初始DP陣列
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...... 50 51 52
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ...... 00 00 00
加入權值5的物品
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...... 50 51 52
01 00 00 00 00 01 00 00 00 00 00 00 00 00 00 00 ...... 00 00 00
加入權值13的物品
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...18... 50 51 52
01 00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 ...01... 00 00 00
加入權值21的物品
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...18...21...26...34...39... 50 51 52
01 00 00 00 00 01 00 00 00 00 00 00 00 01 00 00 ...01...01...01...01...01... 00 00 00
加入權值30的物品
00 01 02 03 04 05 06 07 08 09 10 11 12 13.18.21..26..30..34 35..39..43..48..50 51 52
01 00 00 00 00 01 00 00 00 00 00 00 00 01.01.01..01..01..01 01..01..01..01..00 01 00
加入權值35的物品
00 01 02 03 04 05 06 07 08 09 10 11 12 13.18.21.26.30.34 35.39 40..43..48..50 51 52
01 00 00 00 00 01 00 00 00 00 00 00 00 01.01.01.01.01.01 02.01 01..01..02..00 01 00
最後發現最多塞到51
另一半是104-51=53
53-51=2即為所求
狀態:
k代表放了幾種物品
w是第k種物品的權值
i代表該格的容量
初始值:
dp表格除了dp=1初始值皆為0;
轉移式:
dp]+=dp[ i ];
轉化為背包後的複雜度是o(k*(sum(ni)/2))<=o(20*20*1000)
背包問題是一種經典的問題
此題只是其中一種變形...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 我想法是這樣子 例如:5 13 21 30 35 40
要找差值最小,因為題目說會分成兩堆,我想說每次拿n/2個,並且這樣配對(5,13,21)再跟剩餘的作差值,(5,13,30)再跟剩餘的作差值,(5,13,35)再跟剩餘的作差值..以此類推,接著在變成(5.21.30)再跟剩餘的作差值,(5,21,35)再跟剩餘的作差值...以此類推,之後再變成(5,30,35),(5.30.40),這樣子 回復 4# aa1379aa
其實你的演算法方式我有想過，但有個地方你還沒思考到，
如 poorpoorpoor 所舉之例子
1 1 1 1 1 5，這樣分二堆會是 SetA = {1, 1, 1} , SetB = {1, 1, 5}，但在你的 code 中，我似乎還看不到 SetA/ SetB 之元素個數會有縮減之動作。
不甚確定 DP 問題是否了解其意義或曾 coding 過，若真沒解過 DP 問題，建議先解最基礎的背包問題較佳，附上背包問題
一個小偷到金樓裡面偷東西，每樣東西之重量為 Wi，價值 Vi，
小偷背包最多只能裝 WS 重量，請問小偷要怎麼偷怎可以拿走最多價值之東西？
變型有很多，像每樣東西都只限定一樣，所以就只有決定「拿」或「不拿」，
這是 0/1 背包問題；
另也有「每樣商品之重量為 Wi，價值 Vi，最多數量為 Ci」這種變型，
建議先解簡單的 0/1 背包問題，再回來看 poorpoorpoor 所說，
會較有心得。...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div> 你的作法不太對
如果有6個東西分別是1 1 1 1 1 5
分成(1 1 1 1 1)和(5)加值差距是0
不一定兩堆數量要一樣 ...
poorpoorpoor 發表於 2011-6-24 10:55 PM http://www.eyny.com/images/common/back.gif
阿!!!! 原來容量是總和的一半... 佩服! 我一定會記住的...
我之前做過一道類似的題, 當時的K<=10. 看到別人的AC time還以為是用貪婪法達成的... 不爭氣的我就只能暴力枚舉......<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 回復 5# goodbye_mylove
版主,不好意思,SetA/ SetB 之元素個數會有縮減之動這部份我不知道如何下手寫,所以看不到
可以交交我嗎><! poorpoorpoor大大,感謝你的回覆,我還在努力完成中 poorpoorpoor大大,能解釋一下這部分嗎,還是有點不太懂?
狀態:
k代表放了幾種物品
w是第k種物品的權值
i代表該格的容量
初始值:
dp表格除了dp=1初始值皆為0;
轉移式:
dp]+=dp[ i ]; 如果你不知道什麼是狀態跟轉移建議你先去學動態規劃
也就是所謂的dp
等你大致了解dp是什麼再來做背包問題就會輕鬆許多
如果你要直接用枚舉有兩種方法
1.回溯法
2.枚舉0~(2^k)-1
第i個bit如果是0代表第i個物品在第一堆如果是1代表他在第二堆
下禮拜要段考 先不解釋太多<br><br><br><br><br><div></div> 讓我提供一些動態規劃的資料
動態規劃是由Bellman提出的一種數學方法，主要是藉著記憶法(Memorization)和最優化原理去求得最優解。涉及動態規劃的元素主要有幾個：目標函式、狀態、狀態轉移公式和邊界條件（例如初始狀態的值）。
不過一般來說，便是開一個數組，以它的維(dimension)作為狀態，最後便是找出轉移公式。
給一道題作例：
http://zerojudge.tw/ShowProblem?problemid=b210
http://codepad.org/E3KMBGq0
假若目標函式的狀態牽涉兩個元，便開一個兩維的數組，然後DP。
比方說這一題：http://poj.org/problem?id=3176
狀態是(row,column)，轉移公式是f = max ( f, f )，邊界條件是f = 0。
動態規劃和一般遞歸的主要分別是，動態規劃會使用數組去記住當前狀態的值，避免重複運算或是使用過多的變量。所以，有位前輩說過，動態規劃其實就是做表和填表……
總括而言，動態規劃要設計好狀態、函式、轉移方程和定義邊界條件。寫好這些之後，問題就基本上解決了。
可以參考：
http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html
而背包問題是有相當多的前人探討過，我還未讀完他們寫的文章……我們一起看就好(掩面)
http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/KnapsackProblem.htm
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 感謝大大分享,小弟正在努力理解中 = =+ 回復 7# aa1379aa
>> 版主,不好意思,SetA/ SetB 之元素個數會有縮減之動這部份我不知道如何下手寫
>> ,所以看不到 可以交交我嗎><!
這是舉個例子而已，實際上還是用 DP 去做較為合適，
在我的看法裡，這種方式依舊屬「暴力法」之一種，
建議還是學 DP 較為適當。 DP我怎麼還是搞不太懂,目標函式、狀態、狀態轉移公式 看了例子還是不太懂><!! 回復 14# aa1379aa
這個時候你得說出哪個部份看不懂... 不然可是沒人幫到你呢<br><br><br><br><br><div></div>
頁:
[1]
2