割り振り問題

質問

以下のような問題を解きたいです。（リンゴなのは対象の性質は関係ないから解りやすさのためです）
括弧の中は例として使う数値です

リンゴがnum個入る箱がx個あります。(num = 100個, x = 5箱)
箱にはそれぞれ重要度が書かれています。(ここでは1,2,2,3,3)
重要度は1から∞まであり得、同じ重要度が複数箱ありえます。

初めの状態では、全ての箱にリンゴが入れられるだけ入っています。

まず、箱の中のリンゴを全て出して一カ所に集めます。
そしてそのリンゴのうち、rateパーセントだけ残して全部捨てます。(rate = 80%)

その後余ったリンゴを箱に戻します。
戻すときには、1を最も高い重要度として、各箱に割り当てられた重要度に応じて
リンゴの量に差を付けて戻したいです。

例えば例題では、一箱100個までリンゴが入り全部で500個、そのうち80%だけ残して捨てます。
残った400個のリンゴを、重要度が(1,2,2,3,3)の五つの箱に差を付けて戻したいです。

この差を付けて戻すというところのやり方が、良い方法が浮かびません。
重要度１の箱には可能な限り限界近くまで入れ、それ以外の箱は、一番少ない個数の箱が多くなるように、でもある程度の差は付いているようにしたいです。
例えば例題なら
100,80,80,70,70といったように割り振りたいです。

実際はこの割り振りを解くプログラムを書きたいのですが、どのようにやれば良いでしょうか？

回答No.1

dscripty · ベストアンサー

「重要度は1から∞まであり得。」

重要度が無限大まであるなら、すべての箱に同じ数だけいれれば終わり。

重要度の最大が無限大じゃないなら、最大をどこにするかが抜けているから、プログラムの前に仕様を詰めよう！

例えば、箱の中で最大数の重要度をつけた箱には、りんごを入れない。とか、重要度1 の箱の半分だけ入れるとか。そういう決めごとが、たりないよ？

お礼

なるほど…確かにそういった決まり事をしてないから、頭の中でいくら考えても言い答えが出ないんですね。
ありがとうございます、もう少し細かい条件まで詰めてみますね。