出産前後の痔にはご注意!

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

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

A 回答 (1件)

ナップサック問題なんかだと『アルゴリズム事典』の類に


載ってることがありますが、
複雑になるので、全部は説明できないやね。

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q0-1ナップザック問題の解き方がわからない

報酬が最大となるタスクの組み合わせを求めよという問題があるサイトで出されました
問題の内容からして動的計画法が使えるのかなと思ったのですが、但し書きで「1度タスクをこなしたら、同じタスクをすることができない」と書いてありました
こういうパターンの場合、どういう風に解いていけばいいんでしょうか
検索したら、ある大学のサイトで0-1ナップザック問題の解き方なるものが出てきましたが、解説を読んでもさっぱりわかりませんでした
アイテムを一つしか使えないナップザック問題を動的計画法で解く方法について教えてほしいです

Aベストアンサー

0-1「でない」ナップサック問題に対する動的計画法が理解できていれば何も問題ないはずなんだけどなぁ....

「とる」か「とらない」かの 2択なんだし.


人気Q&Aランキング