質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

1回答

2041閲覧

01ナップサック問題を分枝限定法で解きたいです。

SABA01

総合スコア10

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

1クリップ

投稿2018/08/05 14:15

編集2022/01/12 10:55

#概要
01ナップサック問題を分枝限定法の結果が一致しない。
私は今01ナップサック問題を解こうとしています。
しかし、出力結果が私の思い描いていたものとは違っておりどうすればよいのかわかりません。

データとしては
容量が10のナップサックで入れたいものはそれぞれ、
番号0 W = 4 V = 32
番号1 W = 7 V = 35
番号2 W = 6 V = 24
番号3 W = 3 V = 9
です。

#問題点
本来であれば番号0と3が最適解となるはずなのですが必ず番号0が1、それ以外が0となってしまいます。
コードは下記の通りなのですが、どこが間違っているのでしょうか。
再起条件が間違っているような気がするのですが、再起条件はこれで合ってますでしょうか

public class Main {

Java

1 public static int n= 4;//荷物の数は4とする 2 public static int[] W = new int[n];//重さ 3 public static int[] V = new int[n];//価値 4 public static int c = 10;//荷物の容量 5 public static int z = 0; 6 public static int w = 0; 7 public static int v = 0; 8 public static int[] X = new int[n];//暫定解(リュックに何を入れればよいか)

java

1 public static void main(String[] args){ 2 3 W[0] = 4; 4 W[1] = 7; 5 W[2] = 6; 6 W[3] = 3; 7 8 V[0] = 32; 9 V[1] = 35; 10 V[2] = 24; 11 V[3] = 9; 12 13 Napsack(1);//レベル1を渡す...配列でいう0 14 }

java

1 public static void Napsack(int Level){ 2 if(Level > n){//葉の部分...終端 3 w = W[Level - 1] + w;//更新 4 v = V[Level - 1] + v;//更新 5 if((w <= c) && (v > z)){ 6 z = v;///暫定解を更新する 7 X[Level - 1] = 1; 8 9 } 10 }else{//列挙木の内部 11 w = W[Level - 1] + w;//更新 12 v = V[Level - 1] + v;//更新 13 if(w <= c){//容量を超えない 14 if(c == w){//重量と容量が一致 15 z = v; 16 X[Level - 1] = 1;//暫定解とする 17 }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る 18 X[Level - 1] = 0; 19 Napsack(Level + 1); 20 X[Level - 1] = 1; 21 Napsack(Level + 1); 22 23 } 24 } 25 } 26 27 for(int i = 0; i < n; i++){ 28 System.out.println(X[i]); 29 } 30 31 }

Java

1 public static int max(int l){//ubを決める 2 int max = 0; 3 for(;l < n;l++){//渡された位置より後ろの中でubを定める 4 if(V[l] / W[l] > max){ 5 max = V[l];//最も価値が高いものを選出 6 } 7 } 8 return max; 9 10 }

}

♯01ナップサック問題
容量Cのリュックサック(入れ物)に物を入れていきます。
その時にW(重さ)がC(容量)を超えないように組み合わせて入れていく必要があります。
そうしたときに最もV(価値)が高くなる組み合わせを選ぶというものです。
今回ですと、容量10のナップサックに以下の4つのものを組み合わせて入れていきます。
番号0 W = 4 V = 32
番号1 W = 7 V = 35
番号2 W = 6 V = 24
番号3 W = 3 V = 9
今回の場合ですと最も価値が高くなる、かつCを超えない組み合わせは番号0と番号2の組み合わせになります。

#分枝限定法
上から順番に物を入れるか入れないかの列挙木を作って解いていきます。
そのため、すべての組み合わせを試して行くことになるのですが、その中でこれ以上進めても無駄だろうと判断した場合、それより後の処理をやらずに飛ばしてしまいます。
具体的に言えば上限値が暫定解を下回った場合です。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kei344

2018/08/05 15:29

(質問文は編集できます)質問文のコードはそれぞれコードブロックで囲んでいただけませんか? ```(バッククオート3つ)で囲み、前後に改行をいれるか、コードを選択して「<code>」ボタンを押すとコードブロックになります。また、JAVAとJavaScriptは別言語です。質問タグからJavaScriptを外してください。
SABA01

2018/08/05 15:48 編集

わかりました。やってみましたが、これで出来ていますでしょうか。タグについてはJavaScriptとJavaの違いが判らず2つ付けてしまいました。ご迷惑をおかけいたしました。
y_waiwai

2018/08/05 15:40

01ナップサック問題、というのも分枝限定法、というのも知らないんで解説してくれますか
SABA01

2018/08/05 15:49

わかりました。質問文の方に書かせていただきます。
guest

回答1

0

分岐限定法のアルゴリズムは理解していないですが、この再帰アルゴリズムで問題と思われそうなのは

以下の、「容量を超えた場合」の処理が書かれておらず。

java

1if(w <= c) {//容量を超えない 2 if(c == w){//重量と容量が一致 3 z = v; 4 X[Level - 1] = 1;//暫定解とする 5 }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る 6 X[Level - 1] = 0; 7 Napsack(Level + 1); 8 X[Level - 1] = 1; 9 Napsack(Level + 1); 10 } 11}

以下のように再帰処理を継続していないので、
番号0が暫定解となった次の再帰で、

w = W[Level - 1] + w;//更新の部分が、

番号1のw=7、前の再帰のw=4、となりcを超えるので、再帰が終わっています。

java

1w = W[Level - 1] + w;//更新 2v = V[Level - 1] + v;//更新 3if(w <= c) {//容量を超えない 4 if(c == w){//重量と容量が一致 5 z = v; 6 X[Level - 1] = 1;//暫定解とする 7 }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る 8 X[Level - 1] = 0; 9 Napsack(Level + 1); 10 X[Level - 1] = 1; 11 Napsack(Level + 1); 12 } 13} else { 14 // ここになんらかの処理(再帰)が必要? 15}

投稿2018/08/06 02:59

momon-ga

総合スコア4820

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問