[問題]01背包的分堆變形題

看板 Prob_Solve
作者
時間
留言 12則留言,2人參與討論
推噓 5  ( 5推 0噓 7→ )
先上題目:e900:交換紙牌遊戲 https://zerojudge.tw/ShowProblem?problemid=e900 題目要求和01背包的變形問題-分堆一樣,要求分成兩堆且數字和越接近越好。 但這個題目多了限制就是在最少的翻牌次數...。 這邊提供通過的程式碼:https://ideone.com/qQ5iL5 問題差異: 選某張卡片正面的點數時是加上差值且翻牌次數不變,否則必定選擇反面, 加上「負的差值」且次數多一,分堆問題時只要考慮選不選某個數字, 不選時狀態不變,但這題不選時因為加上「負的差值」狀態會改變。 狀態設定: 狀態改變時會有負數,陣列不能存取負的位置所以需要做偏移, 最糟糕的情況=負最多時,每張牌的範圍是(-12,12),牌數最多1000張, 總和=(-12000,12000) ... 陣列的空間要求。 base(偏移量)=所有牌的負值總和。 初始狀態:用到的數字=0(做完偏移後是 base)且該狀態下翻牌次數=0 cnt[ 目前使用的陣列 ][ 偏移後的數字 ]= 最少的翻牌次數 狀態轉移: 根據第i張牌,只需更新 pvt (上一次有紀錄到的數字),避免重複紀錄這一次更新 到的狀態,只要檢查該格位置是否第一次更新。 不翻:v(新狀態)=pvt+num[0][i]-num[1][i]且 翻牌次數不變 cnt[now][v]=min(cnt[now][v],cnt[pre][pvt]) 翻牌:v(新狀態)=pvt+num[1][i]-num[0][i]且 翻牌次數多一 cnt[now][v]=min(cnt[now][v],cnt[pre][pvt]+1) 輸出時從兩堆差值=0,1(-1 or 1)... 依此類推直到找到第1個次數的狀態不是 INF 就是答案。 --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.222.86.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1602146166.A.333.html ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/08/2020 16:45:03 ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/08/2020 16:55:34 ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/09/2020 12:41:07 ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 10/09/2020 12:44:47
1Fucrxzero: 請問這比leetcode難嗎 10/18 18:19
2Fddavid: leetcode有簡單題也有難題,樓上你想問什麼 10/21 09:06
3Fucrxzero: 找工作需要寫這個嗎 10/21 10:29
4Fddavid: 看你找什麼工作,還有演算法題從來就不只是為了讓你背題到 10/21 13:34
5Fddavid: 時工作解一模一樣的問題 10/21 13:35
6Fddavid: 到時工作你不會直接看到背包問題,卻會用到解題思維以及動 10/21 13:36
7Fddavid: 態規劃、greedy、divide and conquer、tree、graph等等概 10/21 13:37
8Fddavid: 念,寫演算法題是為了讓你懂得怎麼自己思考應用這些概念 10/21 13:38
9Fddavid: 當然你可找個用不上解題思維的工作,但這個版就是解題版XD 10/21 13:40
10Fddavid: 看到你在別的版也問過leetcode的問題,也許我在Python以前 10/21 13:44
11Fddavid: 這篇拋磚的文章可以給你一點參考?XD #1UQl27Mt (Python) 10/21 13:45
12Fucrxzero: OK 10/30 20:53