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