以下のようなC言語プログラムを作成したのですが、実行時間がかかり、より実行時間が短くなるようなプログラムを作成したいです。（以下の条件のどんな入力でも実行時間が3秒以内には収まるようにしたいです。 ） プログラム例または作成のポイントを教えて頂きたいです。（該当するアルゴリズム名もあれば教えて頂きたいです。） A君はx円の所持金があります。このx円の所持金が収まる範囲で、宝石店で複数の宝石を買おうとしています。宝石店にはN種類の宝石があり、それぞれの宝石には価格[w_i]と人気度[r_i]が数字で示されています。A君が宝石の合計人気度を最大になるように宝石を買ったとき、その最大合計人気度を出力するプログラムを作成して下さい。ただし、同じ種類の宝石は買わないとします。 ■条件 1≦N≦100 1≦x≦10,000 1 ≦ w_i ≦ 1,000 (1 ≦ i ≦ N) 1 ≦ r_i ≦ 1,000 (1 ≦ i ≦ N) ■入力は以下のフォーマットで与えます。 N x w_1 r_1 w_2 r_2 ... w_N r_N ■入力例 4 10 2 7 7 1 2 9 4 7 ■出力例(入力例に対する) 23 /*作成したプログラム*/ #include <stdio.h> //最大合計人気度を求める関数（再帰関数） void tensu(int *r_sum_max,int w_sum,int r_sum,int n,int N,int x,short int w[],short int r[]){ if(w_sum>x){ return; } if(*r_sum_max<r_sum)*r_sum_max=r_sum; if(n==(N-1)){ return; } n++; tensu(r_sum_max,w_sum+w[n],r_sum+r[n],n,N,x,w,r); tensu(r_sum_max,w_sum+0,r_sum+0,n,N,x,w,r); return; } int main(void){ char str[100]; char *p; int r_sum_max=0; int N,x; short int w[1100],r[1100]; int i; p=str; fgets(str, sizeof(str), stdin); sscanf(p,"%d %d¥n",&N,&x); for(i=0;i<N;i++){ fgets(str, sizeof(str), stdin); p=str; sscanf(p,"%hd %hd¥n",&w[i],&r[i]); } tensu(&r_sum_max,w[0],r[0],0,N,x,w,r); tensu(&r_sum_max,0,0,0,N,x,w,r); printf("%d¥n",r_sum_max); return 0; }
