学校のプログラミングの授業課題で、貪欲算法を計算結果を出力すべくC言語の実装課題が出題されました。
ファイル名を読み込み、そのファイルに書いてある数値から貪欲算法の結果を出力するプログラムを作成したいのですが、どこから始めればいいのかがわかりません。
貪欲算法とは、例えば、以下のようなある4つの重さと価値を持つ商品があったとき
<4つの商品>
価値 重さ 【単位あたり】
1. 16 2 8
2. 19 3 6.33..
3. 57 10 5.7
4. 28 5 5.6
単位あたりの価値が高いものからナップサックの中に入れ、ナップサックの容量を超えないまでの、価値合計と重さ合計を求めるというもので、仮に今回の問題でナプサックの容量を12としたとき、価値が高いもの順に商品を並べると、No1>NO2>No3>No4となるため、最初にNo1を入れる→その次にNo2を入れる→No3をナップサックの中に入れたいところだが、重さが10あり容量を超えてしまうので、No3よりも価値は低くなるがNo4を入れる。ここで、価値合計は16+19+28=63、重さ合計は2+3+5=10となる。
なので、仮にも「knap4.txt」に、上記のように記載されている場合は、期待している実行結果は以下のようになるはずです。
$./a.out
データファイル名:knap4.txt
ナップサックの容量:12
No. 価値 重さ 単位あたり
1 16 2 8
2 19 3 6.33..
3 57 10 5.7
4 28 5 5.6
価値合計:63 重さ合計:10
ここで、私が必要と感じたことは、まず単位あたりの価値が大きい方からソートをする関数「sort」の作成→「sort」を用いてナップサックの容量を超えないまで商品を入れるための仕様を書き込むこと。
しかし、この問題のひっかけは、単に単位価値が高いものからナップサックの中に入れた場合、No1→No2→No3→No4の順で入れることとなるため、ナップサックの容量を12とした場合、上記の考えだけでは答えは「価値合計:35 重さ合計:5」となってしまうと思うのです。なので、単位価値、重さ、ナップサックの容量の引数を仮に「tanni,omosa,capacity」としたとき、「if(omosa<capasity){printf(...);」などとして、sortを用いたりするような実装手順だと思うのですが、どこから初めていいのかがわかりません。
ちなみに、先生からは以下のプログラムをヒントとして用いて良いと言われました。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int NMOJI=50;
const int MAX_ITEM=100;
int main()
{
FILE *fp;
int i,j;
int nitem;
double capacity;
double weight[MAX_ITEM],value[MAX_ITEM];
char file_name[NMOJI];
printf("Data Flie Name: ");
scanf("%s",file_name);
if((fp=fopen(file_name,"r"))==NULL){
printf("%s:そのファイルを開けることはできません。\n");
return -1;
}
printf("Knapsack capacity: "); scanf("%f",&capacity);
printf("データファイル名: \n",file_name);
printf("ナップサック容量: \n",capacity);
printf("\n");
fscanf(fp"%d",&nitem);
if(nitem>MAX_ITEM){
prinf("アイテム数を%3d以下にしてください.\n",MAX_ITEM);
return -1;
}
for(i=0;i<nitem;i++)
fscanf(fp,"%f",&weight[i]);
for(i=0;i<nitem;i++)
fscanf(fp,"%f",&value[i]);
fclose(fp);
return 0;
}
上記のプログラムにどこにどのような関数を組み合わせたらいいのか、ヒントでもいいので教えてください。お願いします。
73
, 重さの合計は12
になるので、こちらの方が最適解(optimal solution)かと思われます。0-1 Knapsack problem
であるならば、Google Search: "0-1 knapsack problem" "greedy algorithm" が参考になるでしょう。