質問編集履歴
2
ナップサック問題と分枝限定法について追記しました
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
コードをコードブロックに分けました。
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
|
-
|
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
|
}
|