[其他] 怎麼把好幾組數字平均分配

看板Math作者 (法摩拉比漢典)時間9年前 (2015/05/31 18:31), 編輯推噓5(5推 0噓 6→)
留言11則, 6人參與, 最新討論串1/1
情境是這樣的 網路商城滿千折百 但一筆訂單只能折價一次 然後我現在購物車有十幾項商品 累積4000多元的商品了 例如 350 580 270 366 688.......等等 希望能拆成四張一千左右的訂單 要怎麼分配 因為分配不好 有些單價比較高 可能變成某一張訂單超過一千太多 最後一張訂單不足一千了 我都是自己胡亂組合 面對這樣的情況 有比較科學的方式來處理嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.173.158 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1433068295.A.71E.html
推
05/31 18:50, , 1F
先將商品由低價到高價排列，例如100.200.300...900
05/31 18:50, 1F
→
05/31 18:51, , 2F
再利用梯形公式，100+900 200+800 類似這樣即可
05/31 18:51, 2F
推
05/31 20:17, , 3F
先算出有哪些子集合>=1000之後再DP
05/31 20:17, 3F
→
05/31 20:18, , 4F
時間複雜度3^商品數
05/31 20:18, 4F
推
05/31 23:16, , 5F
樓上 那複雜度比爆搜還慘吧 是怎DP的...
05/31 23:16, 5F
推
06/01 00:40, , 6F
先隨機分四群,再把超過最多的補到最不夠的,反覆迭代
06/01 00:40, 6F
→
06/01 00:40, , 7F
,是否可證明在有限次內會完成？直覺應該不用迭代太
06/01 00:40, 7F
→
06/01 00:40, , 8F
多次
06/01 00:40, 8F
→
06/01 00:56, , 9F
解個整數規劃就好了
06/01 00:56, 9F
推
06/01 02:59, , 10F
某樓說的爆搜複雜度是多少讓我瞻仰一下，商品數<20
06/01 02:59, 10F
→
06/01 23:09, , 11F
你把金額貼來讓大夥分析如何
06/01 23:09, 11F
‣ 更多 Lo78 的文章
文章代碼(AID): #1LQkC7SU (Math)