name_knapsack012.cpp

0/1/2背包问题,从文件输入,从文件输出.里面有详细的报告和程序说明文档

// dynamic programming 0/1/2 problem

#include <iostream.h>
#include <stdlib.h>  
// contains max & min functions
#include <stdio.h>
#include "db.h"
#include "max.h"

template<class T>
void Knapsack(T p[], int w[], int c, int n, T** f)
{// 对于所有i and y计算f[i][y] 

   // 初始化 f[n][]
   int yMax = min(w[n]-1,c);
   for (int y = 0; y <= yMax; y++)
      f[n][y] = 0;
   yMax = min(2*w[n]-1,c);
   for (y = w[n]; y <= yMax; y++)
      f[n][y] = p[n];
   for (y = 2*w[n]; y <= c; y++)
      f[n][y] = 2*p[n];
   
   // 计算剩下的 f值
   for (int i = n - 1; i > 1; i--) {
      yMax = min(w[i]-1,c);
      for (int y = 0; y <= yMax; y++)
         f[i][y] = f[i+1][y];
      for (y = w[i]; y <= c; y++)
         f[i][y] = max(f[i+1][y],
                       f[i+1][y-w[i]] + p[i]);
      for (y = 2*w[i]; y <= c; y++)
         f[i][y] = max(f[i][y],
                       f[i+1][y-2*w[i]] + 2*p[i]);
      }
   f[1][c] = f[2][c];
   if (c >= w[1])
      f[1][c] = max(f[1][c], f[2][c-w[1]] + p[1]);
   if (c >= 2*w[1])
      f[1][c] = max(f[1][c], f[2][c-2*w[1]] + 2*p[1]);
}

template<class T>
void Traceback(T **f, T p[], int w[], int c, int n, int x[])
{// Compute x for optimal filling.
   for (int i = 1; i < n; i++)
      if (f[i][c] == f[i+1][c]) x[i] = 0;
      else if (f[i][c] == f[i+1][c-w[i]] + p[i]) {
              x[i] = 1;
              c -= w[i];}
           else {
              x[i] = 2;
              c -= 2*w[i];}

   // compute x[n]
   if (c < w[n]) x[n] = 0;
   else if (c < 2*w[n]) x[n] = 1;
        else x[n] = 2;
}

void main(void)
{
  
   int **f;
   int i;
   int p[50];
   int w[50];
   int x[50];
   int n,c;
   int a[100];
   FILE *fp;    //定义输入文件指针
   FILE *stream;//定义输出文件指针

   //从name_knapsack012.input文件中输入初始数据 

	if((fp=fopen("name_knapsack012.input","r"))==NULL) 
    {  
        cout<<"Can't open the file!"<<endl; 
    }
	fseek(fp, 2, SEEK_SET); //移动句柄所对应的文件的指针fp,偏移量为2字节
	fscanf(fp, "%d", &n);//读n的值
	fseek(fp, 3, SEEK_CUR);
	fscanf(fp, "%d", &c);//读c的值
	fseek(fp, 5, SEEK_CUR);
	    for(i=1;i<=n;i++) //读p[n]
	{
		fscanf(fp, "%d", &p[i]); 
		fseek(fp, 1, SEEK_CUR);
	}  
	    fseek(fp, 5, SEEK_CUR);
  	    for(i=1;i<=n;i++) //读w[n]
	{
			fscanf(fp, "%d", &w[i]);  
			fseek(fp, 1, SEEK_CUR);
	}  
	if(fclose(fp)!=0) 
    { 
		cout<<"File cannot be closed"<<endl;  
    } 

   Make2DArray(f, n+1, c+1);
   Knapsack(p, w, c, n, f);                         //初始化并计算所有的f值
   Traceback(f,p,w,c,n,x);                          //调用回溯函数
   
   //从name_knapsack012.input文件中输入初始数据  
   
   stream=fopen("name_knapsack012.output","w");     //打开输出文件，并指定为stream指针
   fprintf(stream,"The optimal  value are: ");      //写入输出文件，先输出最优值的总和
   fprintf(stream,"%d",f[1][c]); 
   fprintf(stream,"\nThe optimal x's value are: [");//写入输出文件，输出最优值的序列
   for(i=1;i<n;i++)
   fprintf(stream,"%d,",x[i]);
   fprintf(stream,"%d].\nThe f' values are:\n   y",x[n]);
   for(i=0;i<=c;i++)                                //输出f值
   fprintf(stream,"%d  ",i);
   fprintf(stream,"\ni\n");
   for(i=n;i>1;i--)
   {
     fprintf(stream,"%d   ",i);
     for(int j=0;j<=c;j++)
     fprintf(stream,"%d  ",f[i][j]);
     fprintf(stream,"\n");
 }

}