質問編集履歴
1
わからない部分を具体的にしました
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -2,9 +2,9 @@
|
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
5
|
-
ナップサック問題を解いています二次元配列を用いて実現する方法はわかりました。
|
|
5
|
+
ナップサック問題を解いています、二次元配列を用いて実現する方法はわかりました。
|
|
6
6
|
|
|
7
|
-
次に一次元配列を二つ使用
|
|
7
|
+
次に一次元配列を二つ使用する方法や、一つだけ使用して実現する方法を考えているのですが、いまいちどのようにコードを書けばよいかがわかりません。
|
|
8
8
|
|
|
9
9
|
どうかよろしくお願いします。
|
|
10
10
|
|
|
@@ -12,7 +12,31 @@
|
|
|
12
12
|
|
|
13
13
|
ナップサック問題を二次元配列を用いずに実現したい。
|
|
14
14
|
|
|
15
|
+
ソースコードにある二次元配列dpを一次元配列で実現させたい。
|
|
15
16
|
|
|
17
|
+
ここら辺をどうすればいいか悩んでいます
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
```
|
|
22
|
+
|
|
23
|
+
for(i=0;i<=N;i++){
|
|
24
|
+
|
|
25
|
+
for(j=0;j<=M;j++){
|
|
26
|
+
|
|
27
|
+
int x,y=-1;
|
|
28
|
+
|
|
29
|
+
if(i!=0){
|
|
30
|
+
|
|
31
|
+
x = dp[i-1][j];
|
|
32
|
+
|
|
33
|
+
if(j>=w[i])y = dp[i-1][j-w[i]]+v[i];
|
|
34
|
+
|
|
35
|
+
if(x>y)dp[i][j]=x;
|
|
36
|
+
|
|
37
|
+
else dp[i][j]=y;
|
|
38
|
+
|
|
39
|
+
```
|
|
16
40
|
|
|
17
41
|
|
|
18
42
|
|