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

[Lo78 (法摩拉比漢典)]

情境是這樣的

網路商城滿千折百 但一筆訂單只能折價一次

然後我現在購物車有十幾項商品 累積4000多元的商品了

例如 350 580 270 366 688.......等等

希望能拆成四張一千左右的訂單 要怎麼分配


因為分配不好 有些單價比較高

可能變成某一張訂單超過一千太多 最後一張訂單不足一千了

我都是自己胡亂組合 面對這樣的情況 有比較科學的方式來處理嗎

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.173.158
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1433068295.A.71E.html
推 yeskid      : 先將商品由低價到高價排列，例如100.200.300...900
→ yeskid      : 再利用梯形公式，100+900 200+800 類似這樣即可
推 fenzhang    : 先算出有哪些子集合>=1000之後再DP
→ fenzhang    : 時間複雜度3^商品數
推 ScottOAO    : 樓上 那複雜度比爆搜還慘吧 是怎DP的...
推 letssee     : 先隨機分四群,再把超過最多的補到最不夠的,反覆迭代
→ letssee     : ,是否可證明在有限次內會完成？直覺應該不用迭代太
→ letssee     : 多次
→ THEJOY      : 解個整數規劃就好了
推 fenzhang    : 某樓說的爆搜複雜度是多少讓我瞻仰一下，商品數<20
→ nonumber    : 你把金額貼來讓大夥分析如何