0-1ナップサック問題の解法プログラム - yue_agata @Wiki

0-1ナップサック問題の解法プログラム

レポート課題で出たから作った。クイックソートが大変。

#include  <stdio.h>

void QSort(double x[], double w[], double v[], int left, int right);
void Swap(double x[ ], double w[ ], double v[ ], int i, int j);
void ShowData(double x[ ], double w[ ], double v[ ], int n);
void nap(double w[ ], double v[ ], double totalw, double totalv, int i);
void main(void);

 /* クイックソートを行う */
void QSort(double x[], double w[], double v[], int left, int right)
{
    int i, j;
    int pivot;

    i = left;                      /* ソートする配列の一番小さい要素の添字 */
    j = right;                     /* ソートする配列の一番大きい要素の添字 */    

   pivot = x[(left + right) / 2]; /* 基準値を配列の中央付近にとる */

   while (1) {                    /* 無限ループ */
 
       while (x[i] < pivot)       /* pivot より大きい値が */
           i++;                   /* 出るまで i を増加させる */

       while (pivot < x[j])       /* pivot より小さい値が */
           j--;                   /*  出るまで j を減少させる */
       if (i >= j)                /* i >= j なら */
           break;                 /* 無限ループから抜ける */

       Swap(x, w ,v, i, j);             /* x[i] と x[j]を交換 */
       i++;                       /* 次のデータ */
       j--;
   }

   if (left < i - 1)              /* 基準値の左に 2 以上要素があれば */
       QSort(x, left, i - 1);     /* 左の配列を Q ソートする */
   if (j + 1 <  right)            /* 基準値の右に 2 以上要素があれば */
       QSort(x, j + 1, right);    /* 右の配列を Q ソートする */
}
 
 /* 配列の要素を交換する */
void Swap(double x[ ], double w[ ], double v[ ], int i, int j)
{
   double temp, tempw, tempv;

   temp = x[i];
   tempw = w[i];
   tempv = v[i];
   x[i] = x[j];
   w[i] = w[j];
   v[i] = v[j];
   x[j] = temp;
   w[j] = tempw;
   v[j] = tempv;
}


 /* n 個のデータをファイルに出力する */
void ShowData(double x[ ], double w[ ], double v[ ], int n)
{
   int i;
   FILE *fp;
   fp = fopen("sort.txt","a");
   for (i = 0; i < n ; i++)
       fprintf("%d %d %d\n", x[i], w[i], v[i]);
   fclose(fp);
}

void nap(double w[ ], double v[ ], double totalw, double totalv, int i)
{
   while (1)
   {
       totalw+=w[i];
       totalv+=v[i];
if(totalw>260)
{
   totalw-=w[i];
   totalv-=v[i];
   for(;i<26;i++;)
   {
	if(totalw>253)
	{
	   printf("result :weight = %d value = %d\n",totalw, totalv);
	   break;
	}
        else if(260-totalw >= w[i])
	{
	   totalw+=w[i];
	           totalv+=v[i];
	  	   nap(w, v, totalw, totalv, i);
	}
 	   }
}
++i;
   }
}

void main(void)
{      /* ソートする配列 */
   double x[26];
   double w[26];
   double v[26];
   double totalw=0, totalv=0;
   int n = 26;
   FILE *fp;
   FILE *fp2;

   fp = fopen("parcel","r");
   for (i = 0; i < n ; i++)
       fscanf(fp,"%d %d",&w[i], &v[i]);
   fclose(fp);

   for (i = 0; i < n ; i++)
       x[i] = v[i]/w[i] ; /*重量1あたりの価値*/

   QSort(x, w, v, 0, n - 1);

   printf("ソート終了\n");
   ShowData(x, w, v, n);

   fp2 = fopen("sort.txt","r");
   for (i = 0; i < n ; i++)
       fscanf(fp,"%d %d %d",&x[i] ,&w[i], &v[i]);
   fclose(fp);

  nap(w, v, totalw, totalv, 0);
}