C言語でサイゼリヤナップサック問題-再帰
問題
出せる料金の上限値を決め、それを超えないように摂取カロリーが最大になるように商品を選ぶ
そのときの商品名と料金、摂取カロリーを出力せよ
処理の流れ
- ファイルからメニュー表(商品名,カロリー,値段)を取得
- 商品を端から深さ優先探索で取捨選択していく
- 制約として料金の上限値を超えた場合にはその時点でバックトラックしている(つもり)
- 深さ優先探索ですべての商品を考慮し終わったら、その組み合わせと摂取カロリーをそれぞれ配列と変数に持っておく
- 最終的な解を配列と変数から取得、表示
※これからほかの手法(動的計画法、ビット演算)と計算時間を比較したいので
メニュー表
商品名 カロリー コスト 彩りガーデンサラダ 130 299 小エビのサラダ 115 349 やわらかチキンのサラダ 134 299 わかめサラダ 92 299 イタリアンサラダ 196 299 シーフードサラダ 229 599 半熟卵とポークのサラダ 433 599 コーンクリームスープ 142 149 冷たいパンプキンスープ（季節限定） 105 149 たっぷり野菜のミネストローネ（季節限定） 222 299 削りたてペコリーノチーズ 59 100 ミニフィセル 188 169 ガーリックトースト 252 189 辛味チキン 374 299 アスパラガスのオーブン焼き（季節限定） 221 299 ポップコーンシュリンプ 215 299 エスカルゴのオーブン焼き 256 399 ムール貝のガーリック焼き 164 399 野菜ソースのグリルソーセージ 570 399 チョリソー 393 399 柔らか青豆の温サラダ 213 199 ほうれん草のソテー 138 199 キャベツとアンチョビのソテー 80 199 ポテトのグリル 366 199 セロリのピクルス（季節限定） 52 199 真イカのパプリカソース 138 199 フォッカチオ 214 119 プチフォッカ 214 139 セットプチフォッカ 107 79 フレッシュチーズとトマトのサラダ 203 299 フレッシュチーズとトマトのサラダ（Wサイズ） 406 598 プロシュート 162 399 プロシュート（Wサイズ） 324 798 熟成ミラノサラミ 95 299 熟成ミラノサラミ（Wサイズ） 190 598 マルゲリータピザ 568 399 パンチェッタのピザ 646 399 野菜ときのこのピザ 610 399 やわらかイカのアンチョビのピザ 593 499 バッファローモッツァレラのピザ 575 499 ミラノサラミのピザ 606 499 ほうれん草のグラタン（季節限定） 521 399 シーフードグラタン 537 499 アラビアータ 591 399 ミートソースボロニア風 582 399 半熟卵のミートソースボロニア風 672 468 アーリオ・オーリオ 560 299 キャベツのペペロンチーノ 686 399 タラコソースシシリー風 605 399 スープ入りトマト味ボンゴレ（季節限定） 686 499 パルマ風スパゲッティ 700 399 イカの墨入りスパゲッティ 610 499 カルボナーラ 865 499 アスパラガスとエビのクリームスパゲッティ（季節限定） 711 499 アラビアータ（Wサイズ） 1182 770 ミートソースボロニア風（Wサイズ） 1164 770 アーリオ・オーリオ（Wサイズ） 1120 574 キャベツのペペロンチーノ（Wサイズ） 1372 770 タラコソースシシリー風（Wサイズ） 1210 770 パルマ風スパゲッティ（Wサイズ） 1400 770 イカの墨入りスパゲッティ（Wサイズ） 1220 976 カルボナーラ（Wサイズ） 1730 976 アスパラガスとエビのクリームスパゲッティ（季節限定）（Wサイズ） 1422 976 トッピング半熟卵 90 69 ミラノ風ドリア 542 299 半熟卵のミラノ風ドリア 632 368 セットプチフォッカ付きミラノ風ドリア 649 378 いろどり野菜のミラノ風ドリア 590 399 エビとイカのドリア 624 499 シーフードパエリア 602 599 エビと野菜のトマトクリームリゾット 302 399 ハヤシ＆ターメリックライス 638 499 半熟卵のハヤシ＆ターメリックライス 728 568 ミックスグリル 823 599 ハンバーグステーキ 514 399 デミグラスソースのハンバーグ 628 499 野菜ソースのハンバーグ（ディアボラ風） 585 499 イタリアンハンバーグ 633 499 焼肉とハンバーグの盛合せ 709 599 若鶏のグリル（ディアボラ風） 541 499 柔らかチキンのチーズ焼き 588 499 パンチェッタと若鶏のグリル 663 599 リブステーキ 621 999 ライス 303 169 ラージライス 454 219 スモールライス 151 119 カプチーノ（アイスケーキ）（季節限定） 114 199 ティラミス（アイスケーキ） 131 199 シナモンフォッカチオ 246 169 プリンとカプチーノの盛合せ 330 399 プリンとティラミスの盛合せ 347 399 ミルクアイスのせシナモンフォッカチオ 346 319 ミルクジェラート 100 199 シチリア産レモンのソルベ 127 199 イタリアンプリン 216 249 チョコレートケーキ 166 299 コーヒーゼリー 162 299 トリフアイスクリーム 164 369
コード
#include<stdio.h> #include<string.h> #include<time.h> #define MAX_N 110 //商品の最大個数 #define MAX_C 1000 //出せる最大金額 typedef struct MENU{ char name[256]; //商品名 int cal; //カロリー int cost; //値段 }M; int ans[MAX_N]={}; //解 int cand[MAX_N]={}; //解候補 M m[MAX_N]; //商品のデータ int N; //読み込んだ商品の種類数 int max_cal=0; //最大カロリー int costy=0; //最大カロリーを実現するためのコスト void knap(int i,int sum_cal,int sum_cos){ //出せる金額を上回った if(sum_cos>MAX_C) return; //すべての品物について考えた if(i==N){ if(sum_cos<=MAX_C && max_cal<sum_cal){ memcpy(ans,cand,sizeof(cand)); max_cal = sum_cal; costy = sum_cos; } return; } //商品iを入れる cand[i] = 1; knap(i+1,sum_cal+m[i].cal,sum_cos+m[i].cost); //商品iを入れない cand[i] = 0; knap(i+1,sum_cal,sum_cos); return; } int main(void){ FILE *fp; char fname[] = "test.txt"; int cnt=0; clock_t start,end; if((fp = fopen(fname,"r"))==NULL){ printf("errer\n"); return -1; }else{ printf("%s file opened\n",fname); } while(fscanf(fp,"%s %d %d",m[cnt].name,&m[cnt].cal,&m[cnt].cost)!=EOF) cnt++; fclose(fp); N = cnt; //メニュー一覧 printf("%d\n",N); for(int i=0;i<N;i++) printf("name:%s\ncal:%d\ncost:%d\n\n",m[i].name,m[i].cal,m[i].cost); printf("\n"); start = clock(); //開始時刻を取得 knap(0,0,0); //再帰ナップ end = clock(); //終了時刻を取得 //最終解 printf("you should order these! (cost<=%d)\n\n",MAX_C); for(int i=0;i<N;i++){ if(ans[i]==1){ printf("name:%s\ncal:%d\ncost:%d\n\n",m[i].name,m[i].cal,m[i].cost); } } printf("SUM_COST:%dyen\n",costy); //かかるコスト printf("MAXI_CAL: %dcal\n\n",max_cal); //摂取カロリー printf("calc_time:%fs\n\n",(double)(end-start)/CLOCKS_PER_SEC); //計算時間 return 0; }
実行結果
※都合上メニュー一覧は表示せず
you should order these! (cost<=1000) name:ポテトのグリル cal:366 cost:199 name:アーリオ・オーリオ（Wサイズ） cal:1120 cost:574 name:ラージライス cal:454 cost:219 SUM_COST:992yen MAXI_CAL: 1940cal calc_time:0.073000s
想定される解は得られたようだ
