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

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

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

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

受付中

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

SABA01
SABA01

総合スコア0

Java

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

1回答

0評価

1クリップ

87閲覧

投稿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

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

java

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

java

public static void Napsack(int Level){ if(Level > n){//葉の部分...終端 w = W[Level - 1] + w;//更新 v = V[Level - 1] + v;//更新 if((w <= c) && (v > z)){ z = v;///暫定解を更新する X[Level - 1] = 1; } }else{//列挙木の内部 w = W[Level - 1] + w;//更新 v = V[Level - 1] + v;//更新 if(w <= c){//容量を超えない if(c == w){//重量と容量が一致 z = v; X[Level - 1] = 1;//暫定解とする }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る X[Level - 1] = 0; Napsack(Level + 1); X[Level - 1] = 1; Napsack(Level + 1); } } } for(int i = 0; i < n; i++){ System.out.println(X[i]); } }

Java

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

}

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

kei344
kei344

2018/08/05 15:29

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

2018/08/05 15:48 編集

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

2018/08/05 15:40

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

2018/08/05 15:49

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

まだ回答がついていません

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

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

同じタグがついた質問を見る

Java

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