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

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

看板Prob_Solve (計算數學 Problem Solving)作者fatcat8127 (胖胖貓)時間4年前 (2020/10/08 16:36)推噓5(5推 0噓 7→)

留言12則, 2人參與討論串1/1

先上題目：e900:交換紙牌遊戲 https://zerojudge.tw/ShowProblem?problemid=e900 題目要求和01背包的變形問題-分堆一樣，要求分成兩堆且數字和越接近越好。但這個題目多了限制就是在最少的翻牌次數...。這邊提供通過的程式碼：https://ideone.com/qQ5iL5 問題差異：選某張卡片正面的點數時是加上差值且翻牌次數不變，否則必定選擇反面，加上「負的差值」且次數多一，分堆問題時只要考慮選不選某個數字，不選時狀態不變，但這題不選時因為加上「負的差值」狀態會改變。狀態設定：狀態改變時會有負數，陣列不能存取負的位置所以需要做偏移，最糟糕的情況＝負最多時，每張牌的範圍是(-１２，１２)，牌數最多１０００張，總和＝(-１２０００，１２０００) ... 陣列的空間要求。 base(偏移量)＝所有牌的負值總和。初始狀態：用到的數字＝０(做完偏移後是 base)且該狀態下翻牌次數＝０ cnt[ 目前使用的陣列 ][ 偏移後的數字 ]= 最少的翻牌次數狀態轉移：根據第ｉ張牌，只需更新 pvt (上一次有紀錄到的數字)，避免重複紀錄這一次更新到的狀態，只要檢查該格位置是否第一次更新。不翻：ｖ(新狀態)＝pvt+num[０][i]-num[１][i]且翻牌次數不變 cnt[now][v]=min(cnt[now][v],cnt[pre][pvt]) 翻牌：ｖ(新狀態)＝pvt+num[１][i]-num[０][i]且翻牌次數多一 cnt[now][v]=min(cnt[now][v],cnt[pre][pvt]+1) 輸出時從兩堆差值＝０，１(-1 or 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