ナップサック問題を全列挙・分枝限定法・動的計画法の3つの方法で解くプログラムを作成したいです。

前提・実現したいこと

ナップサック問題においてファイル(kp10.data,kp20.data,kp30.data,kp40.data,kp50.data,kp100.data)を読み込んで次の3つの方法で解くプログラムを作成したいです。
1.全列挙
2.分枝限定法
3.動的計画法
ちなみに定義関数のところで示している引数の意味は次の通りです。
n アイテム数
*p 価値配列の先頭を指すポインタ
*w 重さ配列の先頭を指すポインタ
capa 要領
*best 最適解(0,1の値)を入れる配列の先頭を指すポインタ
*profit 最適値(総利益)
*weight 総重量

発生している問題・エラーメッセージ

その中で分枝限定法は上手くいったのですが,全列挙でエラー・動的計画法で場合によってsegmentation faultや出力結果が全て0になったりしています。ポインタの扱い方が曖昧なのでそこもプログラムを参考にして教えて欲しいです。

kp_report.cpp: 関数 ‘int knap(int, int)’ 内:
kp_report.cpp:28:41: エラー: ‘int (*)[n]’ から ‘int’ への無効な変換です [-fpermissive]
  else if(capa < w[i]) profit = knap(i+1,&w);
                                         ^~
kp_report.cpp:25:5: 備考:   initializing argument 2 of ‘int knap(int, int)’
 int knap(int i,int capa) {
     ^~~~
kp_report.cpp:29:29: エラー: ‘int (*)[n]’ から ‘int’ への無効な変換です [-fpermissive]
  else profit = max(knap(i+1,&w),knap(i+1,capa-w[capa])+p[i]);
                             ^~
kp_report.cpp:25:5: 備考:   initializing argument 2 of ‘int knap(int, int)’
 int knap(int i,int capa) {
     ^~~~

dynamic programmig
item :

profit =0   weight = 0   (0sec.)

dynamic programmig
Segmentation fault

該当のソースコード

C++
1#include<iostream>
2#include<algorithm>
3#include<stdio.h>
4#include<string.h>
5#include<time.h>
6using namespace std;
7
8
9void enumeration(int n,int *p,int *w,int capa,int *best,int *profit,int *weight) //全列挙
10{
11	int i = 0;
12	if(i == n) *profit = 0;
13	else if(capa < w[i]) {
14		i++;
15		enumeration(n,p,w,capa,best,profit,weight);
16	}
17	else{
18		i++;
19		;
20	}
21}
22
23
24int knap(int i,int capa) {
25	int n,p[n],w[n],profit;
26	if(i == n) profit = 0;
27	else if(capa < w[i]) profit = knap(i+1,&w);
28	else profit = max(knap(i+1,&w),knap(i+1,capa-w[capa])+p[i]);
29	return profit;
30}
31
32
33void dynamic_programming(int n,int *p,int *w,int capa,int *best,int *profit,int *weight) //動的計画法
34{
35	int y,i,dp[n][capa];
36	for(y=0;y<=capa;y++) dp[n][y] = 0;
37	for(i=0;i<=n;i++){
38		for(y=0;y<=capa;y++){
39			if(y < w[i]) dp[i][y] = dp[i+1][y];
40			else dp[i][y] = max(dp[i+1][y],dp[i+1][y-w[i]+p[i]]);
41					
42		}
43	}
44	*profit = dp[0][capa];
45}
46
47int bb(int n,int *p,int *w,int capa,int *x,int *best,int *ub,int *branch,int *tem,int max,int fix_p,int fix_w,int level,int *count) {
48	int total = fix_w;
49	(*count)++;
50	branch[level] = -1;
51	int i = 0;
52	int j = 0;
53	ub[level] = fix_p;
54	while(total < capa && i < n) {
55		if(x[i] < 0) {
56			if(w[i] <= capa - total) {
57				total += w[i];
58				ub[level] += p[i];
59				tem[j++] = i;
60			}
61			else {
62				ub[level] += (double)p[i]*(capa-total)/w[i];
63				total = capa;
64				branch[level] = i;
65			}
66		}
67		i++;
68	}
69	tem[j] = -1;
70	if(ub[level] > max) {
71		if(branch[level] < 0) {
72			max = ub[level];
73			for(i=0,j=0;i<n;i++) {
74				if(i == tem[j]) {
75					best[i] = 1;
76					j++;
77				}
78				else if(x[i] == 1)
79					best[i] = 1;
80				else
81					best[i] = 0;
82			}
83		}
84		else {
85			j = branch[level];
86			if(fix_w + w[j] <= capa) {
87				x[j] = 1;
88				max = bb(n,p,w,capa,x,best,ub,branch,tem,max,fix_p+p[j],fix_w+w[j],level+1,count);
89			}
90			x[j] = 0;
91			max = bb(n,p,w,capa,x,best,ub,branch,tem,max,fix_p,fix_w,level+1,count);
92			x[j] = -1;
93		}
94	}
95	return max;
96}
97
98void branch_and_bound(int n,int *p,int *w,int capa,int *best,int *profit,int *weight) //分枝限定法
99{
100	int x[n],ub[n],branch[n],tem[n];
101	for(int i=0;i<n;i++){
102		x[i]=-1;
103		best[i]=0;
104	}
105	int count=0;
106	*profit=bb(n,p,w,capa,x,best,ub,branch,tem,0,0,0,0,&count);
107	*weight=0;
108	for(int i=0;i<n;i++)
109		if(best[i]==1)
110			*weight+=w[i];
111	cout<<"No.of nodes:"<<count<<endl;
112}
113
114void output(int n,int *best,int *trans,int profit,int weight,double ex_time)
115{
116	cout << "item :" << endl;
117	for(int i=0;i<n;i++)
118		if(best[trans[i]] == 1)
119			cout << " " << i+1;
120	cout << endl;
121	cout << "profit =" << profit << "   weight = " << weight << "   (" << ex_time  << "sec.)" << endl;
122}
123
124int main(int argc, char** argv)
125{
126	clock_t	start, end;
127
128	if(argc != 2){
129		cout << "usage: " << argv[0] << "(data file name)" << endl;
130		return -1;
131	}
132	char filename[50];
133	strcpy(filename,argv[1]);
134	FILE	*fp = fopen(filename,"r");
135	if(fp == NULL){
136		cout << filename << " cannot be opend" << endl;
137		return -1;
138	}
139
140/********** data input *************/
141	int n;
142	fscanf(fp,"%d",&n);
143	int p[n], w[n], capa;
144	for(int i=0;i<n;i++)
145		fscanf(fp,"%d",&p[i]);
146	for(int i=0;i<n;i++)
147		fscanf(fp,"%d",&w[i]);
148	fscanf(fp,"%d",&capa);
149	fclose(fp);
150
151/********** sort items by p[i]/w[i] *************/
152	int t[n], trans[n];
153	for(int i=0;i<n;i++)
154		t[i] = i;
155	for(int i=0;i<n-1;i++)
156		for(int j=i+1;j<n;j++)
157			if((double)p[i]/w[i] < (double)p[j]/w[j]) {
158				int temp = p[i];
159				p[i] = p[j];
160				p[j] = temp;
161				temp = w[i];
162				w[i] = w[j];
163				w[j] = temp;
164				temp = t[i];
165				t[i] = t[j];
166				t[j] = temp;
167			}
168	for(int i=0;i<n;i++)
169		trans[t[i]] = i;	// original item number
170
171	double	ex_time;
172	int best[n], profit= 0, weight = 0;
173
174/********** enumeration *************/
175/*
176	cout << endl << "enumeration" << endl;
177	start = clock();
178	cout << knap(0,capa) << endl;
179	end = clock();
180	ex_time = (double)(end - start) / CLOCKS_PER_SEC;
181	output(n,best,trans,profit,weight,ex_time);
182*/
183/********** dynamic programmig *************/
184	profit= 0, weight = 0;
185	cout << endl << "dynamic programmig" << endl;
186	start = clock();
187	dynamic_programming(n,p,w,capa,best,&profit,&weight);
188	end = clock();
189	ex_time = (double)(end - start) / CLOCKS_PER_SEC;
190	output(n,best,trans,profit,weight,ex_time);
191/********** branch and bound *************/
192	cout <<endl << "branch and bound" << endl;
193	start = clock();
194	branch_and_bound(n,p,w,capa,best,&profit,&weight);
195	end = clock();
196	ex_time = (double)(end - start) / CLOCKS_PER_SEC;
197	output(n,best,trans,profit,weight,ex_time);
198
199	return 0;
200}

ファイルのデータ

//kp10.data どのデータも上から要素数, 価値と重量, 容量の順で表されています。
10

  40  50  19  36   7  15   9  13  13  26

 112 152  44 106 109 194 131 167 170 133


659

//kp20.data
20

  40  50  19  36   7  15   9  13  13  26  18   8  50  12  15  50  37  23  26  39

 118  48 173  69 181  24 150 193 165 170 152  28 191  25  36 121 145 111  63  85


1124

//kp30.data
30

  40  50  19  36   7  15   9  13  13  26  18   8  50  12  15  50  37  23  26  39  24  54  29  25  37  30  56  49  21  26

 152  28 191  25  36 121 145 111  63  85 164 102 111  37  77  32 130 198  76  92 191 145 135  26  30  31 128 127 144 135


1534

//kp40.data
40

  40  50  19  36   7  15   9  13  13  26  18   8  50  12  15  50  37  23  26  39  24  54  29  25  37  30  56  49  21  26   8  34  47  31  42  27  51  17  19  41

 164 102 111  37  77  32 130 198  76  92 191 145 135  26  30  31 128 127 144 135 105 161 150  21  57 133 173  14  91 110 120   6  96  50 128 120  98  25 197  50


2008

//kp50.data
50

  40  50  19  36   7  15   9  13  13  26  18   8  50  12  15  50  37  23  26  39  24  54  29  25  37  30  56  49  21  26   8  34  47  31  42  27  51  17  19  41  20   8  17  43  33  38  36  54  32  48

 191 145 135  26  30  31 128 127 144 135 105 161 150  21  57 133 173  14  91 110 120   6  96  50 128 120  98  25 197  50 157 185  94  46   8 107 110 155 153  66 184 139   2  91 131 138 196  57 164  12


2596

//kp100.data
100

   7  40  50  19  36   7  15   9  13  13  26  18   8  50  12  15  50  37  23  26  39  24  54  29  25  37  30  56  49  21  26   8  34  47  31  42  27  51  17  19  41  20   8  17  43  33  38  36  54  32  48  47  51  41  32  36  37  34  33  50  41  11  17  56  27  13  39  29  20  47  16  26  12  52  56  34  26  54  31  53  56  13  41  50  52  14  13  16  11   9  22  40  45   8  47  37  44  52  13  20

  12 428  43 107 469 213   2  11 481 159  72 332 315 348  65 198 126 439 432  19 488 152 188 414 180 496 251 251 414  63 135 274  48  22 331 141  58 179 227   4  98 409 394 489 239  86  94 189 221 212 247 388 211 210 388 169 104 474 401 175 106 184 453 371 288 303 411 406 111 401 497 143  86 361  48 425 232 159 387 220 401 416  56 183 375  62   7 103 269 366 471  19 224  90 107 320 131 156 233 494

11930

試したこと

上のプログラムにあるように全列挙ではint knapで戻り値を設定する方法とvoid enumerationで戻り値を設定しない方法で実装してみました。本来はvoidの法で実行したいです。また, profitやw,p　などをポインタ引数としておいているため, 再帰を実行するときに&をつけたり*をつけたりしました。

補足情報

C++17を使用しています。

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

回答1件

ベストアンサー

int dp[n][capa]; は配列の要素数が定数ではありません。
C++ には、Cのような可変長配列の機能はないのですが、
GNU の拡張仕様でエラーになっていません。

このように要素数が宣言された配列の要素を dp[i][j] で参照する場合、
i は 0～(n-1)、j は 0～(capa-1) でなければなりません。
dp[n][y] = 0; の n は範囲外であり、y も capa になるので範囲外です。
これが segmentation fault の原因です。
w[i] も i は 1～(n-1) でないといけないのに w[n] を参照しています。

追記
関数の引数が多いのは面倒なので、クラスを使ってみました。

C++
1#include <iostream>
2#include <fstream>
3#include <vector>
4using namespace std;
5
6class Knapsack {
7	int n, capa, max_profit, max_weight;
8	vector<int> p, w, u, best;
9public:
10	bool input(const char* fname) {
11		ifstream ifs(fname);
12		if (!ifs) return false;
13		ifs >> n;
14		p.resize(n);
15		w.resize(n);
16		for (int i = 0; i < n; i++) ifs >> p[i];
17		for (int i = 0; i < n; i++) ifs >> w[i];
18		ifs >> capa;
19		max_profit = 0;
20		u.resize(n);
21		best.resize(n);
22		return true;
23	}
24
25	void step(int i, int profit, int weight) {
26		if (i == n) {
27			if (weight <= capa && profit > max_profit) {
28				max_profit = profit;
29				max_weight = weight;
30				best = u;
31			}
32		}
33		else if (weight <= capa) {
34			u[i] = 0; step(i+1, profit, weight);
35			u[i] = 1; step(i+1, profit + p[i], weight + w[i]);
36		}
37	}
38			
39	void solve() { step(0, 0, 0); }
40
41	void output() {
42		cout << "item:";
43		for (int i = 0; i < n; i++)
44			if (best[i]) cout << " " << i+1;
45		cout << "\n"  "profit = " << max_profit
46			<< "  weight = " << max_weight << "\n";
47	}
48};
49
50int main(int argc, char *argv[])
51{
52	if (argc != 2) {
53		cout << "usage: " << argv[0] << " file_name\n";
54		return 1;
55	}
56	Knapsack ks;
57	if (!ks.input(argv[1])) {
58        cout << "can't open " << argv[1] << "\n";
59        return 1;
60    }
61	ks.solve();
62	ks.output();
63}

追記2
n個のアイテムをナップサックに入れるか入れないかを 1 か 0 で表すと、
全列挙とは nビットの数値(00...000～11...111)になります。
11...111 は、(1<<n) - 1。

C++
1#include <iostream>
2#include <fstream>
3#include <vector>
4using namespace std;
5
6class Knapsack {
7    int n, capa, best_profit, best_weight;
8    vector<int> p, w, item, best;
9public:
10    bool input(const char* fname) {
11        ifstream ifs(fname);
12        if (!ifs) return false;
13        ifs >> n;
14        p.resize(n);
15		w.resize(n);
16        for (int i = 0; i < n; i++) ifs >> p[i];
17        for (int i = 0; i < n; i++) ifs >> w[i];
18        ifs >> capa;
19        best_profit = 0;
20        item.resize(n);
21		best.resize(n);
22        return true;
23    }
24
25	void solve() {
26		int m = 1 << n;
27		for (int bp = 0; bp < m; bp++) {  // bit pattern
28			int profit = 0, weight = 0;
29			for (int i = 0; i < n; i++) {
30				if (bp>>i & 1) {
31					item[i] = 1;
32					profit += p[i];
33					weight += w[i];
34				}
35				else item[i] = 0;
36			}
37			if (weight <= capa && profit > best_profit) {
38				best = item;
39				best_profit = profit;
40				best_weight = weight;
41			}
42		}
43	}
44
45    void output() {
46        cout << "item:";
47        for (int i = 0; i < n; i++)
48            if (best[i]) cout << " " << i+1;
49        cout << "\n"  "profit = " << best_profit
50            << "  weight = " << best_weight << "\n";
51    }
52};
53
54int main(int argc, char *argv[])
55{
56    if (argc != 2) {
57        cout << "usage: " << argv[0] << " file_name\n";
58        return 1;
59    }
60    Knapsack ks;
61    if (!ks.input(argv[1])) {
62        cout << "can't open " << argv[1] << "\n";
63        return 1;
64    }
65    ks.solve();
66    ks.output();
67}