Re: ナップサック問題について
Posted: 2017年12月17日(日) 17:46
以前ナップサック問題についてのトピックを立てたものです。プログラミング初心者です。
goods[]を6個から37個に増やしたところ、動作終了と出てしまいます。
品物は重複をしないように選択されるようにしたいのですが、どのように変更すればよろしいでしょうか？
ご指導お願いします。
goods[]を6個から37個に増やしたところ、動作終了と出てしまいます。
品物は重複をしないように選択されるようにしたいのですが、どのように変更すればよろしいでしょうか？
ご指導お願いします。
#include <stdio.h>
#include <memory.h>
// 適当にナップサックに入れる商品リストを定義する
struct Goods
{
int no;
char name[80];
int weight; //各要素の重量
int price; //価値を最大にしたい
}goods[] = {
//価値は男女合計値
{1 ,"a" ,21 , 9},
{2 ,"b" ,23 , 28},
{3 ,"c" ,20 , 8},
{4 ,"d" ,34 , 14},
{5 ,"e" ,18 , 2},
{6,"f",43, 56},
{7,"g",24, 6},
{8,"h",35, 5},
{9,"i",21,4},
{10,"j",25, 3},
{11,"k",39, 4},
{12,"l",37, 5},
{13,"m",45, 40},
{14,"n",20, 12},
{15,"o",12, 3},
{16,"p",47, 40},
{17,"q",44, 17},
{18,"r",173, 73},
{19,"s",133, 63},
{20,"t",48, 9},
{21,"u",13, 3},
{22,"v",13, 8},
{23,"w",11, 8},
{24,"x",13, 4},
{25,"y",92, 40},
{26,"z",132, 70},
{27,"aa",38, 8},
{28,"bb",29, 7},
{29,"cc",59, 21},
{30,"dd",104, 51},
{31,"ee",8, 2},
{32,"ff",76, 54},
{33,"gg",37, 14},
{34,"hh",35, 8},
{35,"ii",18, 4},
{36,"jj",105, 25},
{37,"kk",46, 8},
};
void main()
{
const int KNAP_SIZE_MAX = 600; // ナップサックに入る最大重量
int item[KNAP_SIZE_MAX+1] = {0};
int value[KNAP_SIZE_MAX+1] = {0};
int item_index[KNAP_SIZE_MAX+1] = {0}; // 入れた商品の添字+1
for( int j=0; j<sizeof(goods)/sizeof(Goods); j++ ){ // 商品分のループ
for( int i=1; i<=KNAP_SIZE_MAX; i++ ){ // ナップサックサイズのループ
int knapSpace = i - goods[j].weight;
if( knapSpace >=0 && knapSpace <= KNAP_SIZE_MAX ){
int newValue = value[knapSpace] + goods[j].price;
if( newValue > value[i] && item_index[knapSpace] < j + 1){ // 今の候補よりいい感じ、かつ前に入れた商品より先の商品のみ入れる
value[i] = newValue;
item[i] = goods[j].no;
item_index[i] = j + 1;
}
}
}
}
// 結果表示
for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
printf( "%4d,", value[i] );
}
printf("\n");
for( int i=1; i <= KNAP_SIZE_MAX; i++ ){
printf( "%4d,", item[i] );
}
printf("\n");
printf("ナップサックに入れるもの\n");
int count = 0;
int inItem[KNAP_SIZE_MAX]; // ナップサックに入れる最適な商品
memset( inItem, -1, sizeof(inItem) );
int nokori = KNAP_SIZE_MAX; // ナップサックの残りサイズ
do{
int inItem_ = nokori;
nokori = nokori - goods[ item[nokori] ].weight;
inItem[count++] = item[inItem_];
}while( nokori != 0 );
for( int i=0; i < KNAP_SIZE_MAX; i++ ){
if( inItem[i] > -1 ){
printf( "%d:%s, ", inItem[i], goods[ inItem[i] ].name );
}
}
printf("\n");
}