[問題] 判斷數字可否平均分配

看板C_and_CPP作者 (522)時間11年前 (2012/10/31 00:12), 編輯推噓13(13推 0噓 17→)
留言30則, 11人參與, 最新討論串1/1
請問一下 我遇到了一個題目是說讓使用者輸入一串數字，例如: 5 1 6 7 1 2 假設這些數字要分給兩個人，兩個人拿到的數字總和要一樣大 如果可以讓兩個人拿到的一樣多，那這題就成立，否則不成立 所以上面的例題的解答為成立，分別為5+6跟1+7+1+2 如果使用者輸入的是10 1 2 9 3 則程式輸出不成立，因為並沒有辦法平均分配給兩個人 ====================================== 這題已經想好久了，可是都解不出來 不曉得有沒有高手可以給予提示的? 目前我的方法是先判斷總和是否是偶數，不是偶數的話就直接顯示不成立 例如5 1 6 7 1 2的總和為22，是偶數的話就把他除2也就是11 接著就是去跑雙層for迴圈來判斷是否有哪些數字相加後可以等於11 如果等於11的話那就顯示成立，可是這個for迴圈一直寫不出來， 想請問各位是否有其他的方法?謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 120.124.132.57
→
10/31 01:04, , 1F
為什麼覺得雙層for可以解決？
10/31 01:04, 1F
推
10/31 01:05, , 2F
玩過天平嗎QQ?
10/31 01:05, 2F
推
10/31 01:06, , 3F
google一下partition problem
10/31 01:06, 3F
推
10/31 01:12, , 4F
10/31 01:12, 4F
推
10/31 02:14, , 5F
Q_Q樓上運氣真不錯欸
10/31 02:14, 5F
推
10/31 08:58, , 6F
我怎麼覺得這題沒這麼單純 =.= 樓上大大的解法好像輸入
10/31 08:58, 6F
→
10/31 08:58, , 7F
1 1 1 1 1 1 就不行了欸?
10/31 08:58, 7F
推
10/31 09:08, , 8F
哀呀 沒看清楚...我以為只要兩個數字就好了XD
10/31 09:08, 8F
推
10/31 09:27, , 9F
subset sum = 1/2 sum?
10/31 09:27, 9F
推
10/31 09:29, , 10F
輸入n個數字到陣列input[n] 總和為max，bool dp[max]
10/31 09:29, 10F
→
10/31 09:29, , 11F
for(int i=0; i<n; i++){
10/31 09:29, 11F
→
10/31 09:29, , 12F
for(int i=max; i>0; i--){
10/31 09:29, 12F
→
10/31 09:30, , 13F
if(dp[i]) dp[i + input[j]] = true; }}
10/31 09:30, 13F
→
10/31 09:30, , 14F
最後判斷dp[max/2] 是不是true就好。第二行改成int j=max
10/31 09:30, 14F
→
10/31 09:31, , 15F
dp一開始dp[0]是true，此外都是false
10/31 09:31, 15F
推
10/31 14:12, , 16F
dp[]的意義是?
10/31 14:12, 16F
→
10/31 14:12, , 17F
我應該問dp[i] i是甚麼?
10/31 14:12, 17F
→
10/31 14:52, , 18F
i j 反了
10/31 14:52, 18F
→
10/31 14:58, , 19F
dp 應該是指 dynamic programming
10/31 14:58, 19F
→
10/31 15:00, , 20F
這裡 dp[i] 應該是用來存"有沒有辦法湊出 i"
10/31 15:00, 20F
推
10/31 15:42, , 21F
一開始dp[0~10]為 10000000000
10/31 15:42, 21F
→
10/31 15:43, , 22F
把5丟進去後變成 10000100000 此時dp[5]為true表示可湊5
10/31 15:43, 22F
→
10/31 15:43, , 23F
再丟2進去變成 10100101000 此時dp[2,5,7] 為true
10/31 15:43, 23F
→
10/31 15:44, , 24F
也就是2和5可以湊出2,5,7這三種數字 以此類推
10/31 15:44, 24F
請問你的意思是像這樣嗎? int n=6 int input[n]={5,1,6,7,1,2} int sum=5+1+6+7+1+2 //總和22 int half_sum=sum/2 //一半11 bool dp[sum]={false}; dp[0]=true; for(int i=0;i<n;++i) for(int j=max;j>0;++j) if(dp[i]) dp[ i + input[j] ] = true; 可是if(dp[i]) i是0，第0個位置為true 所以把 dp[ i + input[j]] 也就是dp[ 0 + input[22]]的位置改為true 可是input的範圍只有0~5不是嗎@@? ※ 編輯: yoll522 來自: 120.124.132.57 (10/31 16:39)
推
10/31 16:57, , 25F
j和i好像反了XD if(dp[j]) dp[j + input[i]] = true 才對
10/31 16:57, 25F
→
10/31 16:58, , 26F
然後中間是j的for迴圈是j--從後往前找
10/31 16:58, 26F
推
10/31 17:00, , 27F
反正基本概念就是設一個陣列 假設叫dp 則dp[n]代表目前的
10/31 17:00, 27F
→
10/31 17:01, , 28F
數字有沒有辦法湊出n
10/31 17:01, 28F
推
10/31 18:32, , 29F
你可以 google partition problem ，有不少解釋
10/31 18:32, 29F
→
10/31 22:17, , 30F
瞭解了，感謝各位的幫忙
10/31 22:17, 30F
‣ 更多 yoll522 的文章
文章代碼(AID): #1GZ_o98p (C_and_CPP)