01ナップサック問題を分枝限定法で解く

Question

【編集いたしました】
＃前提・実現したいこと
私は現在JavaScriptを用いて０１ナップサック問題を分枝限定法で解くプログラムを書いています。
流れとしては荷物の個数をもとに列挙木を作り、暫定解をもとに最適でない解が見つかれば再起を用いて１つ前の葉に戻ればよいのではないかと考えておりますがうまく実装ができません。

＃発生している問題
そこで質問なのですが、上限値及び、下記コード内の「ナップザック内の荷物を解の候補とする」はどのように実装すればよいのでしょうか。荷物の有無を保存する配列を作ればよいのですか？また、再起の条件はあっていますでしょうか。
＃ソースコード

w = 重量
z = 暫定解
c = 容量
x[] = 木の高さ
n = 荷物の個数

Napsack(level){
if(level > n){//列挙木の葉の部分？
w =
v =
if((w <= c) && (v > z)){
z = v;
ナップザック内の荷物を解の候補とする;
}
}else{
w =
v =
if(!(w > c)){//重量が荷物の重さを上回ったら打ち切り
if(w == c){//暫定解の更新
if( v > z ){
z = v;
ナップザック内の荷物を解の候補とする;
}
}else if(上限値が暫定解より小さい){
x[level] = 0;
Napsack(level + 1);
x[level] = 1;
Napsack(level + 1);
}
}
}
}

追記
私の不適切な質問のせいで多くの方に不快感を与えてしまい申し訳ありません。
当方このようなサイトを使うことが初めてであり、情報不足、モラル不足だったのだと実感しました。
プログラムの程を実際に書いてみましたのでぜひ皆様のお力を借りれたら幸いです。

Comments

[m.ts10806]

https://teratail.com/help/avoid-asking >何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。

[m.ts10806]

あと「JavaScript」は何の関係があるのでしょうか。質問するときのヒント[ https://teratail.com/help/question-tips ]を熟読して質問を再編してください。

[SABA01]

もうしわけありませんでした。

Answer 1

分枝限定法をつかう競技プログラミング問題をまとめているサイトがありました。

競技プログラミングにおける枝刈り問題まとめ - はまやんはまやんはまやん

上で紹介されているそれぞれのサイトで他の人が書いた回答や解説が閲覧できる場合があります。それらを参考にしてみてください。

Comments

[SABA01]

ご丁寧にありがとうございます。
参考にさせていただきました。とても分かりやすいサイトでうまく出来たと思ったのですが、問題が発生し、未だ完成には至っておりません。そのため別枠で質問させていただきました。この度は私の質問に答えてくださり誠にありがとうございました。