- 締切済み
この問題の計算方法・公式について悩んでいます。
まず、この質問を投稿するまでExcelカテゴリで質問させていただいていたのですが、「計算方法が分からないのでExcelでどう処理したらいいのかわからない」というような内容の回答をいただいてしまったため、一旦打ち切ってこちらで質問させていただくことにした次第です。 宜しくお願いいたします。 様々な商品があります。1円以上9999円以下で、個数は今後増えていくため決まっていません。 これらの商品を袋詰めしていくのですが、１つの袋に商品の値段の合計が１万円以上になるようにしたいです。かつ、使う袋の数は多ければ多いほど良いです。 例えば・・・ 1000、2000、3000、4000、5000、6000円の６個(21000円)の場合、1000+3000+6000=10000、2000+4000+5000=11000で２袋作れます。1000+2000+3000+4000=10000、5000+6000=11000でも同じく２袋となります。袋の数が最大であれば、商品の袋への分配パターンは特にこだわりません。 8000円５個(40000円)の場合は２袋となります。３袋に分配しようとするとどうしても8000円(１万円未満)の袋が出来てしまうためです。 1000、2000、3000、・・・、8000、9000円の９個(45000円)の場合、ちょうど10000円の袋が４つ、余った5000円の商品は適当にどれかの袋に加えるとして、とにかく４袋作ることができます。これを３袋に詰めるようなやり方は上記の「使う袋の数は多ければ多いほど良い」に反します。 例をあげるときりが無いのでこのくらいにしますが、今回皆様のお知恵をお借りしたいのは、 １．ある時点で手元にある商品を上手に袋分けしたら、最大でいくつの袋を作れるか。 ２．袋の数が最大になるように商品をどう分ければよいか(１パターン分かればよい)。 ３．また、もう１つ商品を追加して袋の数をさらに増やせるのであれば、最低いくらの商品を追加すればよいか。 以上３点です。 何かあれば補足します。宜しくお願いいたします。
- みんなの回答 （9）
- 専門家の回答
みんなの回答
- f272
- ベストアンサー率46% (8620/18438)
> ２の「近似解」というのが今いちピンとこないのですが、例を挙げていただけないでしょうか。 例えば#1で示されているのが近似解です。最大で3袋が作れるというのが真の解ですが，近似解ではそれが見つけられない場合もあるということです。 > また、３の考え方を一般論のように説明していただけないでしょうか。 今ある解を見て，あわせても10000円に満たない商品の金額に追加して10000円にするだけの話でしょ。
- f272
- ベストアンサー率46% (8620/18438)
800/900/1200/1400/1900/2100/2200/2600/2700/2900/3100/3500/4700 データ数13、合計30000 このデータでやってみると 4700 3100 2200 3500 2900 2700 900 2600 2100 1900 1400 1200 800 の3袋にするのが正解だ。 一般には １．ある時点で手元にある商品を上手に袋分けしたら、最大でいくつの袋を作れるか。 全部の和（上の例では30000）を10000で割った数を超えない最大の整数が，最大になることは明らかですが，それが実際にできるかどうかはわからない。もしかしたら違うかもと思ってステップ2でトライしてみる。 ２．袋の数が最大になるように商品をどう分ければよいか(１パターン分かればよい)。 近似解で満足できないのなら，すべての組み合わせを確かめるしかありません。近似解でよければ色々と方法はある。 ３．また、もう１つ商品を追加して袋の数をさらに増やせるのであれば、最低いくらの商品を追加すればよいか。 上の例だと 4700 3500 1900 3100 2900 2700 1400 2600 2200 2100 1200 900 800 +200すれば袋が作れる。 具体例があれば簡単だよね。
補足
回答ありがとうございます。 ２の「近似解」というのが今いちピンとこないのですが、例を挙げていただけないでしょうか。 また、３の考え方を一般論のように説明していただけないでしょうか。（一応、具体例を書くのを避けていましたので。）
- maiko0318
- ベストアンサー率21% (1483/6969)
＞検証の結果、反例が出た 反例書いてみ、潰してやるから。 それなりに時間かけて回答してんだよ、こっちは。
補足
そう言っていただけると心強いです。こちらとしても４か月持ち越しの難題でして・・・。 800/900/1200/1400/1900/2100/2200/2600/2700/2900/3100/3500/4700 データ数13、合計30000 例えば、これだとどうなるでしょうか。 ちなみに実際のデータでは合計がまだ10000に届いておらず、書く意味が無い気がするので、省略します。
- maiko0318
- ベストアンサー率21% (1483/6969)
＞あとNo.3の回答については、結局どういうアイデアなのか 一番高いもの、一番安いものを探しまわることなくデータを取り出すことができます。
- maiko0318
- ベストアンサー率21% (1483/6969)
手助けになるかどうか。少し考えてみました。 まず、データを高い順と安い順の２種類作ります。 一番高いデータは高い順リストの一番上に有ります。 一番安いデータは安い順リストの一番上に有ります。 使ったデータは金額を０にし、 データを探すときに無視して次のデータを使います。 データが全て０になったら終了。 でいかがでしょう。
- maiko0318
- ベストアンサー率21% (1483/6969)
誤→４）残金を10.000にリセットし、２袋目として２）へ戻る。 正→４）残金を10.000にリセットし、２袋目として１）へ戻る。 ですね。
- maiko0318
- ベストアンサー率21% (1483/6969)
まず、商品の値段の高いものから並べます。 １）１袋目に、一番高い商品を入れます。 ２）10,000円を超えれば４）へ。 ３）10.000円－１）を計算、値段が正なら（残金あり） 残った商品の安いものから見ていき、計算結果を超える物があればそれを入れます。 なければ一番高い商品を入れ、２）へ。 ４）残金を10.000にリセットし、２袋目として２）へ戻る。 でいかがでしょう。
補足
No.1=No.2=No.3様、回答ありがとうございます。 ただ、その案は前回の質問でも既にいただいており、検証の結果、反例が出たので没になった案です。質問文の分かりやすさを考慮して書くのをやめましたが、きちんと書けばよかったですね。 あとNo.3の回答については、結局どういうアイデアなのかよくわからないのですが・・・。二重に抽出するのを防ぐ、わけでもないですよね・・・。
補足
何度もありがとうございます。 ２について そういう意味でしたらやはり却下せざるをえません。これら一連の質問を投稿する以前から、自分でもアイデアが思いついては消え、思いついては消えの繰り返しで、また同じアイデアをいただくことになってしまいかねません。（というか、既にそうなっています。） ３について たった今気づいたのですが、３のアイデアはNo.6=No.7の（袋の最大数を誤って出した）例をもとに答えていただいたのですね。御手数ですが、No.8の１の例で３の説明をしていただけますか？ つまり・・・ No.8の１の例では合計30000円の商品を３袋（全て１万円以上）に分けることができます。ここにさらに１商品を加えて４袋にできるならば、最低いくらの商品を加えればよいか。 この問題を、「明らかに１万円」ではなく、あらゆる場合にも使える方法で説明していただきたいのです。