質問編集履歴

2

ナップサック問題と分枝限定法について追記しました

2018/08/05 16:04

投稿

SABA01
SABA01

スコア10

test CHANGED
File without changes
test CHANGED
@@ -1,6 +1,6 @@
1
1
  #概要
2
2
 
3
- 01ナップサック問題を分枝限定法を用ての解き方
3
+ 01ナップサック問題を分枝限定法の結果が一致しな
4
4
 
5
5
  私は今01ナップサック問題を解こうとしています。
6
6
 
@@ -8,8 +8,6 @@
8
8
 
9
9
 
10
10
 
11
-
12
-
13
11
  データとしては
14
12
 
15
13
  容量が10のナップサックで入れたいものはそれぞれ、
@@ -193,3 +191,35 @@
193
191
 
194
192
 
195
193
  }
194
+
195
+
196
+
197
+ ♯01ナップサック問題
198
+
199
+ 容量Cのリュックサック(入れ物)に物を入れていきます。
200
+
201
+ その時にW(重さ)がC(容量)を超えないように組み合わせて入れていく必要があります。
202
+
203
+ そうしたときに最もV(価値)が高くなる組み合わせを選ぶというものです。
204
+
205
+ 今回ですと、容量10のナップサックに以下の4つのものを組み合わせて入れていきます。
206
+
207
+ 番号0 W = 4 V = 32
208
+
209
+ 番号1 W = 7 V = 35
210
+
211
+ 番号2 W = 6 V = 24
212
+
213
+ 番号3 W = 3 V = 9
214
+
215
+ 今回の場合ですと最も価値が高くなる、かつCを超えない組み合わせは番号0と番号2の組み合わせになります。
216
+
217
+
218
+
219
+ #分枝限定法
220
+
221
+ 上から順番に物を入れるか入れないかの列挙木を作って解いていきます。
222
+
223
+ そのため、すべての組み合わせを試して行くことになるのですが、その中でこれ以上進めても無駄だろうと判断した場合、それより後の処理をやらずに飛ばしてしまいます。
224
+
225
+ 具体的に言えば上限値が暫定解を下回った場合です。

1

コードをコードブロックに分けました。

2018/08/05 16:04

投稿

SABA01
SABA01

スコア10

test CHANGED
File without changes
test CHANGED
@@ -36,11 +36,15 @@
36
36
 
37
37
 
38
38
 
39
- #コード
40
39
 
41
- public class Main {
42
40
 
41
+ public class Main {
42
+
43
+
44
+
45
+ ```Java
46
+
43
- public static int n= 4;//荷物の数は4とする
47
+ public static int n= 4;//荷物の数は4とする
44
48
 
45
49
  public static int[] W = new int[n];//重さ
46
50
 
@@ -56,7 +60,11 @@
56
60
 
57
61
  public static int[] X = new int[n];//暫定解(リュックに何を入れればよいか)
58
62
 
63
+ ```
59
64
 
65
+
66
+
67
+ ```java
60
68
 
61
69
  public static void main(String[] args){
62
70
 
@@ -86,7 +94,11 @@
86
94
 
87
95
  }
88
96
 
89
-
97
+ ```
98
+
99
+
100
+
101
+ ```java
90
102
 
91
103
  public static void Napsack(int Level){
92
104
 
@@ -120,7 +132,7 @@
120
132
 
121
133
  X[Level - 1] = 1;//暫定解とする
122
134
 
123
- }else if( + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る
135
+ }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る
124
136
 
125
137
  X[Level - 1] = 0;
126
138
 
@@ -150,7 +162,11 @@
150
162
 
151
163
  }
152
164
 
153
-
165
+ ```
166
+
167
+
168
+
169
+ ```Java
154
170
 
155
171
  public static int max(int l){//ubを決める
156
172
 
@@ -172,4 +188,8 @@
172
188
 
173
189
  }
174
190
 
191
+ ```
192
+
193
+
194
+
175
195
  }