ナップサック問題を一次元の配列を使って解きたい

前提・実現したいこと

ナップサック問題を解いています、二次元配列を用いて実現する方法はわかりました。
次に一次元配列を二つ使用する方法や、一つだけ使用して実現する方法を考えているのですが、いまいちどのようにコードを書けばよいかがわかりません。
どうかよろしくお願いします。

発生している問題

ナップサック問題を二次元配列を用いずに実現したい。
ソースコードにある二次元配列dpを一次元配列で実現させたい。
ここら辺をどうすればいいか悩んでいます

  for(i=0;i<=N;i++){
    for(j=0;j<=M;j++){
      int x,y=-1;
      if(i!=0){
    x = dp[i-1][j];
    if(j>=w[i])y = dp[i-1][j-w[i]]+v[i];
    if(x>y)dp[i][j]=x;
    else dp[i][j]=y;

該当のソースコード

c
1#include <stdio.h>
2#define M 10
3#define N 5
4
5int w[N+1]={0,2,3,4,5,6};
6int v[N+1]={0,4,5,8,9,11};
7int dp[M+1][M+1];
8
9int main(void){
10  int i,j,k;
11  for(i=0;i<=M;i++)for(j=0;j<=M;j++)dp[i][j]=0;
12
13  for(i=0;i<=N;i++){
14    for(j=0;j<=M;j++){
15      int x,y=-1;
16      if(i!=0){
17    x = dp[i-1][j];
18    if(j>=w[i])y = dp[i-1][j-w[i]]+v[i];
19    if(x>y)dp[i][j]=x;
20    else dp[i][j]=y;
21      }
22      printf("%2d ",dp[i][j]);
23    }
24    printf("\n");
25  }
26  printf("\nanswer = %d\n",dp[N][M]);
27  return 0;
28}

補足情報（FW/ツールのバージョンなど）

c言語

jimbe

2022/01/05 18:38

>いまいちわかりません何が分からないのか分かりません。

actorbug

2022/01/06 11:34

まずは、「ナップサック問題一次元配列」あたりで検索しましょう。以下のページにも、まずは自分で検索するように書かれています。質問するときのヒント 1-2. 投稿前に検索し、できるところまで自分でやってみましょう https://teratail.com/help/question-tips#questionTips1-2

行動規範の内容に同意します

回答3件

ベストアンサー

二次元配列を一次元配列に機械的に置き換えると、

c
1#include <stdio.h>
2#define M 10
3#define N 5
4#define K(i,j) ((i)*(M+1)+(j))  // 2変数を一次元配列の添字に変換
5
6int w[N+1]={0,2,3,4,5,6};
7int v[N+1]={0,4,5,8,9,11};
8int dp[(M+1)*(M+1)];  // dp は一次元配列
9
10int main(void){
11  int i,j,k;
12  for(i=0;i<=M;i++)for(j=0;j<=M;j++)dp[K(i,j)]=0;
13
14  for(i=0;i<=N;i++){
15    for(j=0;j<=M;j++){
16      int x,y=-1;
17      if(i!=0){
18        x = dp[K(i-1,j)];
19        if(j>=w[i])y = dp[K(i-1,j-w[i])]+v[i];
20        if(x>y)dp[K(i,j)]=x;
21        else dp[K(i,j)]=y;
22      }
23      printf("%2d ",dp[K(i,j)]);
24    }
25    printf("\n");
26  }
27  printf("\nanswer = %d\n",dp[K(N,M)]);
28  return 0;
29}

結果だけを得られれば良いのであれば、こんな風にも書けます。

C
1#include <stdio.h>
2
3#define M 10
4#define N 6
5
6int w[N] = { 0, 2, 3, 4, 5, 6 };
7int v[N] = { 0, 4, 5, 8, 9, 11 };
8int dp[N], m;  // dp は一次元配列
9
10void f(int i, int w0, int v0)
11{
12	if (w0 > M) return;
13	if (v0 > m) m = v0;
14	if (i < N) {
15		dp[i] = 1; f(i+1, w0 + w[i], v0 + v[i]);
16		dp[i] = 0; f(i+1, w0, v0);
17	}
18}
19
20int main(void)
21{
22	f(0, 0, 0);
23	printf("answer = %d\n", m);
24}