Classical Algorithms (2) - 0/1 Backpack Problem (Dynamic Programming Approach)

/**/ /************************************************************************
* :: 0/1 backpack problem solved (visual studio 2005)
* :: Given a load of m and n items with a weight of wi and a value of vi, 1<=i<=n
* :: Requirement: to load items into knapsacks and maximize the value of the items contained therein
 ************************************************************************/

#include  < >
#include  < >
#include  < string .h >

#define  FILENAMELENGTH 100

class  CBeibao
... {
public:
    int m_nNumber;        //Number of items
    int m_nMaxWeight;    //Maximum load capacity

    int *m_pWeight;        //Weight per item
    int *m_pValue;        //Value of each item

    int *m_pCount;        //Number of times each item is selected
    int m_nMaxValue;    //maximum value

public:
    CBeibao(const char *filename);
    ~CBeibao();
    
    int GetMaxValue();
    int GetMaxValue(int n,int m,int *w,int *v,int *c);
    void Display(int nMaxValue);
    void Display(int nMaxValue,const char *filename);
} ;

// read data
CBeibao::CBeibao( const   char   * filename)
... {
    FILE *fp=fopen(filename,"r");    
    if(fp==NULL)
    ...{
        printf("can not open file!");
        return;    //exit(0);
    }

    //Number of items to be read in and maximum load capacity
    fscanf(fp,"%d%d",&m_nNumber,&m_nMaxWeight);

    m_pWeight=new int[m_nNumber+1];
    m_pValue=new int[m_nNumber+1];

    m_pWeight[0]=0;
    //Read in the weight of each item
    for(int i=1;i<=m_nNumber;i++)
        fscanf(fp,"%d",m_pWeight+i);

    m_pValue[0]=0;
    //Read in the value of each item
    for(int i=1;i<=m_nNumber;i++)
        fscanf(fp,"%d",m_pValue+i);

    //Initialize the number of times each item is selected to 0
    m_pCount=new int[m_nNumber+1];
    for(int i=0;i<=m_nNumber;i++)
        m_pCount[i]=0;

    fclose(fp);
}

CBeibao:: ~ CBeibao()
... {
    delete[] m_pWeight;
    m_pWeight=NULL;
    delete[] m_pValue;
    m_pValue=NULL;
    delete[] m_pCount;
    m_pCount=NULL;
}

/**/ /************************************************************************
* :: Dynamic planning to find the maximum value to satisfy the maximum capacity
* :: Description of parameters: n: number of items
* :: m: backpack load capacity
* :: w: array of weights
* :: v: Array of values
* :: c: Whether the array is selected or not
* :: Return value: maximum value
 ************************************************************************/
int  CBeibao::GetMaxValue( int  n, int  m, int   * w, int   * v, int   * c)
... {
    int row=n+1;
    int col=m+1;

    int i,j;    //Cyclic variable: the first i items can be loaded into a backpack of load capacity j

    //value[i][j] denotes the maximum value of the first i items that can fit into the items in the backpack with load capacity j
    int **value=new int*[row];
    for(i=0;i<row;i++)
        value[i]=new int[col];

    //Initialize row 0
    for(j=0;j<col;j++)
        value[0][j]=0;

    //Initialize column 0
    for(i=0;i<row;i++)
        value[i][0]=0;

    //count
    for(i=1;i<row;i++)
    ...{
        for(j=1;j<col;j++)
        ...{
            //w[i]>j, the ith item is not loaded into the backpack
            value[i][j]=value[i-1][j];
            //w[i]<=j, and the value of the ith item loaded into the backpack >value[i-1][j], then record the current maximum value
            int temp=value[i-1][j-w[i]]+v[i];
            if(w[i]<=j && temp>value[i][j])
                value[i][j]=temp;
        }
    }

    //Backward looking for loaded items
    j=m;
    for(i=row-1;i>0;i--)
    ...{
        if(value[i][j]>value[i-1][j])
        ...{
            c[i]=1;
            j-=w[i];
        }
    }

    //Recording Maximum Value
    int nMaxVlaue=value[row-1][col-1];

    //Release the two-dimensional array
    for(i=0;i<row;i++)
    ...{
        delete [col]value[i];
        value[i]=NULL;
    }
    delete[] value;
    value=NULL;

    return nMaxVlaue;
}

int  CBeibao::GetMaxValue()
... {
    int nValue=GetMaxValue(m_nNumber,m_nMaxWeight,m_pWeight,m_pValue,m_pCount);
    m_nMaxValue=nValue;
    return nValue;
}

// Show results
void  CBeibao::Display( int  nMaxValue)
... {
    printf("   %d ",nMaxValue);
    for(int i=1;i<=m_nNumber;i++)
    ...{
        if(m_pCount[i])
            printf("  %d  %d ",i,m_pCount[i]);
    }
    printf(" ");
}

void  CBeibao::Display( int  nMaxValue, const   char   * filename)
... {
    FILE *fp=fopen(filename,"w");    
    if(fp==NULL)
    ...{
        printf("can not write file!");
        return;    //exit(0);
    }

    fprintf(fp,"%d ",nMaxValue);
    for(int i=1;i<=m_nNumber;i++)
    ...{
        if(m_pCount[i])
            fprintf(fp,"%d  %d ",i,m_pCount[i]);
    }
    fclose(fp);
}

// Show menu
void  show_menu()
... {
    printf("--------------------------------------------- ");
    printf("input command to test the program ");
    printf("   i or I : input filename to test ");
    printf("   q or Q : quit ");
    printf("--------------------------------------------- ");
    printf("$ input command >");
}

void  main()
... {
    char sinput[10];
    char sfilename[FILENAMELENGTH];

    show_menu();

    scanf("%s",sinput);
    while(stricmp(sinput,"q")!=0)
    ...{
        if(stricmp(sinput,"i")==0)
        ...{
            printf("  please input a filename:");
            scanf("%s",sfilename);

            //Getting the best value for meeting maximum loads
            CBeibao beibao(sfilename);
            int nMaxValue=();
            if(nMaxValue)
            ...{
                (nMaxValue);
                int nlen=strlen(sfilename);
                strcpy(sfilename+nlen-4,"_result.txt");
                (nMaxValue,sfilename);
            }
            else
                printf("   error! please check the input data! ");
        }

        //input command
        printf("$ input command >");
        scanf("%s",sinput);
    }
}