さまざまな値段のついた数多くの商品を袋詰めするのですが、1つの袋に詰める商品の値段の合計が全ての袋について1万円以上になるようにしつつ、袋の数をできる限り多くしたい、という前提です。
例えば、8000円の商品が7個あるとした場合(合計56000円)、袋を3つ用意して、ある袋に3個、別の袋に2個、また別の袋に2個入れることで条件を満たします。
もし4つの袋に分けようとすると、どうしても8000円の商品1個だけしか入らない袋ができてしまうため、上記の「全ての袋について1万円以上」という条件を満たしません。
また、2つの袋に分ける方法は、「袋の数をできる限り多くしたい」という条件に合いません。
よって、この場合は袋を3つ用意するのが最適解となります。
その上で、袋をもう1つ増やすために商品を1個追加するとしたら、最低何円の商品を追加すればよいか求めたいです。
上記の例だと、2000円の商品を追加すれば3袋から4袋に増やせることが感覚的に分かっていただけると思います。あるいは、「8000円の商品7個と1999円以下の商品1個を用いて、1万円以上の組み合わせを4組作ることはできないだろう」と。
しかし、現在手元にあるデータはキリのいい数字ばかりでなく、しかも1つずつの商品はもっと安い値段なので、感覚的に捉える事ができず、だからといって「1円追加したら・・・2円追加したら・・・」とアルゴリズム的にやっていく気にもなれません。
そこで、今回の質問は以下のようになります。
「1万円以下の商品が複数あり、それら全てを上手に袋に詰め分けることで、全ての袋を1万円以上にしつつ、袋の数を最大にできたという前提で、
最低で何円の商品を1個追加すれば、袋をさらに1つ増やせるか」
この「何円」の部分を素早く求めたいのです。
ちなみに、この質問は以前から投稿させていただいている問題の一部で、先日も同様の質問をさせていただいていたのですが、いただいた回答が「袋の数を最大にできていない前提」でのアイデアだったため、参考にならないと判断せざるを得ませんでした。
以上、宜しくお願いいたします。
A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
結論として、
『そこで、今回の質問は以下のようになります。
「1万円以下の商品が複数あり、それら全てを上手に袋に詰め分けることで、全ての袋を1万円以上にしつつ、袋の数を最大にできたという前提で、
最低で何円の商品を1個追加すれば、袋をさらに1つ増やせるか」
この「何円」の部分を素早く求めたいのです。』
に、一般的な解はありません。
つまり、任意のn個の商品(価格はそれぞれP1~Pn)で成立している状態に、n+1個目の商品(価格Pn-1)を加えたときの最適なアクションは、他のn個の商品の分割状態によって一意に定まらず、数学的帰納法によってこのような命題を満たす一般化をめざすのは不可能であり得策ではない、のです。
おおもとの目的である『さまざまな値段のついた数多くの商品を袋詰めするのですが、1つの袋に詰める商品の値段の合計が全ての袋について1万円以上になるようにしつつ、袋の数をできる限り多くしたい』というのは非常にわかりやすく身近な問題です。
ただ、それを如何に数学的・アルゴリズム的に「簡略な」「試行錯誤を最小化した」ものにできるか、というのは、あまり思いつきの切り口にこだわらないほうがいいのです。
少なくとも n個で成り立つ状態から n+1個で成り立つ状態を一意に導けるという先入観は捨てたほうがいいでしょう。その付け足した1個のせいで、それなら、すでにつめた袋からこれを抜いて入れ替えて、その抜いたのをさらに別の袋から抜いたのと入れ替えて、そうやっているうちに安い小物がたくさん小銭のようにたまって規定額をオーバーしていた袋から、そこそこの価格の商品を全部抜いていって、新しい一袋ができる、など、様々なことが起こり得るのです。
まあ、日本の硬貨(1,5,10,50,10,500円玉)を、お年玉のためにかき集めて、さあ1000円以上のお年玉袋をたくさん準備しよう、としているほうが、その金銭感(≠金銭感覚)で、コインの入れ替えのイメージをつけやすく、当初の問題につながるアプローチが得られやすいと思いますよ。
おっしゃる通りで、入れ替えの作業がとても面倒だと感じたので、特にこの部分を自動化できればと思ったのですが、ロジックアイデアが1つ出ては多くの例外ケースをもって消え、1つ出ては消え、1つ出ては消えで、どうしようもなくなり投稿させていただいたわけです。
お年玉のアイデアは思いつきませんでしたね。六元連立不等式でしょうか、それを9999元に応用できればいいですが、現段階ではアイデアを思いつきません。この件は改めて投稿させていただこうと思います。
この質問については未解決終了とします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- アルバイト・パート ファミマバイトについて トレーニング中のバイト高校生です。 レジを店長から教えてもらったのですが全然 3 2023/01/04 15:05
- その他(家事・生活情報) スーパーにあるパウダードライアイスって 2 2023/04/08 15:56
- お菓子・スイーツ PB商品の袋入スナック菓子は、100円(税入108円)で売られています。 PB商品の袋入スナック菓子 1 2023/07/30 12:43
- Amazon 新規でAmazon商品ページ作成方法について 1 2022/03/28 00:22
- その他(ニュース・時事問題) 都市部の無人販売店での万引き事件はビジネス方式に問題があるのでは。 8 2022/06/11 20:00
- スーパー・コンビニ ウーバーイーツの件で知恵袋でこのような質問をしたらめちゃくちゃ叩かれました…私がおかしいのでしょうか 11 2022/08/24 07:31
- 食べ物・食材 カルディにお詳しい方への質問 2 2023/01/10 21:05
- 大学・短大 至急お願いします 2 2022/04/26 13:59
- Visual Basic(VBA) vbaマクロについて 次のようなマクロを組みたいです。 自分は初心者なので全くわかりません。 詳しく 8 2023/05/18 18:38
- その他(ネットショッピング・通販・ECサイト) 転売されてしまった商品を取り返そうと検索していたらフリマサイトや大手会社ではない聞いたことのないサイ 5 2022/08/25 21:22
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
袋の折れ目を直せますか?写真...
-
町内会のお祭りの寄付金
-
「袋 大丈夫ですか」
-
接客でも袋について
-
ツルハのレジ 変だと思いませ...
-
物を借りた際の紙袋やビニール...
-
布袋や薬袋のように袋が付く苗...
-
親にばれないようにオナニーを...
-
女性のGスポットの場所について...
-
ビニール包装のティッシュの開け方
-
スマホの軽さを維持しつつ、背...
-
針刺し事故について
-
男性に質問です。 女性と話して...
-
こんにちは。 ミニトマトについ...
-
デリヘルについて教えてくださ...
-
バルサンを焚いて1週間ほど締め...
-
膣外射精どこに出しますか?
-
「ましょうか」は丁寧?
-
プラスチック表面が、経年使用...
-
【緊急】服に付いたサビの落とし方
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
物を借りた際の紙袋やビニール...
-
袋の折れ目を直せますか?写真...
-
町内会のお祭りの寄付金
-
「袋 大丈夫ですか」
-
ツルハのレジ 変だと思いませ...
-
GU紙袋有料化
-
ショップ袋いらないんだけど断...
-
緊急です!!! 卒業式(3月22日...
-
手土産について 得意先に手土産...
-
接客でも袋について
-
食パンの袋が欲しい
-
ローソンのからあげクンの爪楊枝
-
シリアルの一食分って?
-
スーパーのレジで袋もほしかっ...
-
お守りの袋
-
親にばれないようにオナニーを...
-
女性のGスポットの場所について...
-
デリヘルについて教えてくださ...
-
男性に質問です。 女性と話して...
-
ボクは病気です!花ぬ山率のん...
おすすめ情報