ナップサック問題について

質問

価値の高いもの順に物をナップサックにいれていく
のですが入る量が決まっています。
高い順に一から十まであるとして、

for(i=0;i<10;i++)
{ total = total+a[]
total<Max
}
って感じにしたいんですが
途中で越えてしまったらそれはいれずに
次のをいれて最後まで入るかどうか試す
プログラムにしたいです。
入れる順番は価値が高い順って決まってます
この部分だけわからないのでお願いします。

回答No.1

liar_adan · ベストアンサー

ナップサック問題なんかだと『アルゴリズム事典』の類に
載ってることがありますが、
複雑になるので、全部は説明できないやね。

で、ヒントだけ。
「価値」の入っている配列を使うのだと思いますが、
もう一つ「もう入れたか？」のフラグ配列を別に用意し、
どれを入れたかを管理します。
そのフラグを立てたり消したりしながら、
条件に合う組み合わせを探します。