贊助廠商

娛樂城推薦

首頁

電腦與網際網路/其他:電腦列表

計算數學 Problem Solving- 01背包的分堆變形題

先上題目:e900:交換紙牌遊戲https://zerojudge.tw/ShowProblem?problemid=e900題目要求和01背包的變形問題-分堆一樣,要求分成兩堆且數字和越接近越好。但這個題目多了限制就是在最少的翻牌次數...。這邊提供通過的程式碼:https://ideone.com/qQ5iL5問題差異:選某張卡片正面的點數時是加上差值且翻牌次數不變,否則必定選擇反面,加上「負的差值」且次數多一,分堆問題時只要考慮選不選某個數字,不選時狀態不變,但這題不選時因為加上「負的差值」狀態會改變。狀態設定:狀態改變時會有負數,陣列不能存取負的位置所以需要做偏移,最糟糕的情況=負最多時,每張牌的範圍是(-12,12),牌數最多1000張,總和=(-12000,12000) ... 陣列的空間要求。base(偏移量)=所有牌的負值總和。初始狀態:用到的數字=0(做完偏移後是 base)且該狀態下翻牌次數=0cnt[ 目前使用的陣列 ][ 偏移後的數字 ]= 最少的翻牌次數狀態轉移:根據第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 就是答案。--
  • 發問日期:2021-06-01 22:30:19

友站連結