効率よく補数を求める方法について

質問

さまざまな値段のついた数多くの商品を袋詰めするのですが、１つの袋に詰める商品の値段の合計が全ての袋について１万円以上になるようにしつつ、袋の数をできる限り多くしたい、という前提です。

例えば、8000円の商品が７個あるとした場合(合計56000円)、袋を３つ用意して、ある袋に３個、別の袋に２個、また別の袋に２個入れることで条件を満たします。
もし４つの袋に分けようとすると、どうしても8000円の商品１個だけしか入らない袋ができてしまうため、上記の「全ての袋について１万円以上」という条件を満たしません。
また、２つの袋に分ける方法は、「袋の数をできる限り多くしたい」という条件に合いません。
よって、この場合は袋を３つ用意するのが最適解となります。

その上で、袋をもう１つ増やすために商品を１個追加するとしたら、最低何円の商品を追加すればよいか求めたいです。
上記の例だと、2000円の商品を追加すれば３袋から４袋に増やせることが感覚的に分かっていただけると思います。あるいは、「8000円の商品７個と1999円以下の商品１個を用いて、１万円以上の組み合わせを４組作ることはできないだろう」と。

しかし、現在手元にあるデータはキリのいい数字ばかりでなく、しかも１つずつの商品はもっと安い値段なので、感覚的に捉える事ができず、だからといって「１円追加したら・・・２円追加したら・・・」とアルゴリズム的にやっていく気にもなれません。

そこで、今回の質問は以下のようになります。
「１万円以下の商品が複数あり、それら全てを上手に袋に詰め分けることで、全ての袋を１万円以上にしつつ、袋の数を最大にできたという前提で、
最低で何円の商品を１個追加すれば、袋をさらに１つ増やせるか」

この「何円」の部分を素早く求めたいのです。

ちなみに、この質問は以前から投稿させていただいている問題の一部で、先日も同様の質問をさせていただいていたのですが、いただいた回答が「袋の数を最大にできていない前提」でのアイデアだったため、参考にならないと判断せざるを得ませんでした。

以上、宜しくお願いいたします。

回答No.1

trytobe

結論として、

『そこで、今回の質問は以下のようになります。
「１万円以下の商品が複数あり、それら全てを上手に袋に詰め分けることで、全ての袋を１万円以上にしつつ、袋の数を最大にできたという前提で、
最低で何円の商品を１個追加すれば、袋をさらに１つ増やせるか」

この「何円」の部分を素早く求めたいのです。』

に、一般的な解はありません。

つまり、任意のｎ個の商品（価格はそれぞれＰ1～Ｐn）で成立している状態に、n+1個目の商品（価格Ｐn-1）を加えたときの最適なアクションは、他のｎ個の商品の分割状態によって一意に定まらず、数学的帰納法によってこのような命題を満たす一般化をめざすのは不可能であり得策ではない、のです。

おおもとの目的である『さまざまな値段のついた数多くの商品を袋詰めするのですが、１つの袋に詰める商品の値段の合計が全ての袋について１万円以上になるようにしつつ、袋の数をできる限り多くしたい』というのは非常にわかりやすく身近な問題です。

ただ、それを如何に数学的・アルゴリズム的に「簡略な」「試行錯誤を最小化した」ものにできるか、というのは、あまり思いつきの切り口にこだわらないほうがいいのです。

少なくとも ｎ個で成り立つ状態から n+1個で成り立つ状態を一意に導けるという先入観は捨てたほうがいいでしょう。その付け足した１個のせいで、それなら、すでにつめた袋からこれを抜いて入れ替えて、その抜いたのをさらに別の袋から抜いたのと入れ替えて、そうやっているうちに安い小物がたくさん小銭のようにたまって規定額をオーバーしていた袋から、そこそこの価格の商品を全部抜いていって、新しい一袋ができる、など、様々なことが起こり得るのです。

まあ、日本の硬貨（1,5,10,50,10,500円玉）を、お年玉のためにかき集めて、さあ１０００円以上のお年玉袋をたくさん準備しよう、としているほうが、その金銭感（≠金銭感覚）で、コインの入れ替えのイメージをつけやすく、当初の問題につながるアプローチが得られやすいと思いますよ。

お礼

おっしゃる通りで、入れ替えの作業がとても面倒だと感じたので、特にこの部分を自動化できればと思ったのですが、ロジックアイデアが１つ出ては多くの例外ケースをもって消え、１つ出ては消え、１つ出ては消えで、どうしようもなくなり投稿させていただいたわけです。

お年玉のアイデアは思いつきませんでしたね。六元連立不等式でしょうか、それを９９９９元に応用できればいいですが、現段階ではアイデアを思いつきません。この件は改めて投稿させていただこうと思います。
この質問については未解決終了とします。