背包问题(动态规划法).docx

0/1背包问题

 1. 问题描述

          给定一个载重量为m，n个物品，其重量为wi，价值为vi，1<=i<=n，要求:把物品装入背包，并使包内物品价值最大

2. 问题分析

         在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。

         循环变量i，j意义：前i个物品能够装入载重量为j的背包中
         (n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值
         若w[i]>j，第i个物品不装入背包
         否则，若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）

          计算最大价值的动态规划算法如下：

    //计算
    for(i=1;ij,第i个物品不装入背包
            value[i][j]=value[i-1][j];
            //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值
            int temp=value[i-1][j-w[i]]+v[i];
            if(w[i]<=j && temp>value[i][j])
                value[i][j]=temp;
        }
    }

      即该段程序完成以下n个阶段：
     1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值
     2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值
     。。。
     n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值

3. 问题求解

      确定装入背包的具体物品，从value[n][m]向前逆推：
           若value[n][m]>value[n-1][m]，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-w[n]的背包中
           否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中

      以此类推，直到确定第一个物品是否被装入背包为止。逆推代码如下：

    //逆推求装入的物品
    j=m;
    for(i=row-1;i>0;i--)
    {
        if(value[i][j]>value[i-1][j])
        {
            c[i]=1;
            j-=w[i];
        }
    }

4. 代码如下

      输入数据及输出数据均在文件中。
      输入数据格式：
            n m
            w1 w2 ... wn
            v1 v2 ... vn
      输出数据格式：
           maxValue
           i count            //i表示物品编号，count表示该物品被选中次数
           ...

/************************************************************************
 * 0/1背包问题求解 (visual studio 2005)
 * 给定一个载重量为m,及n个物品,其重量为wi,价值为vi,1<=i<=n
 * 要求:把物品装入背包,并使包内物品价值最大
 ************************************************************************/

#include io.h>
#include 
#include 

#define FILENAMELENGTH 100

class CBeibao
{
public:
    int m_nNumber;        //物品数量
    int m_nMaxWeight;    //最大载重量

    int *m_pWeight;        //每个物品的重量
    int *m_pValue;        //每个物品的价值

    int *m_pCount;        //每个物品被选中的次数
    int m_nMaxValue;    //最大价值

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);
};

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

    //读入物品数量和最大载重量
    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;
    //读入每个物品的重量
    for(int i=1;i<=m_nNumber;i++)
        fscanf(fp,"%d",m_pWeight+i);

    m_pValue[0]=0;
    //读入每个物品的价值
    for(int i=1;i<=m_nNumber;i++)
        fscanf(fp,"%d",m_pValue+i);

    //初始化每个物品被选中次数为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;
}

/***********************************************************
 * 动态规划求出满足最大载重量的最大价值
 * 参数说明：n:物品个数
 *           m:背包载重量
 *           w:重量数组
 *           v:价值数组
 *           c:是否被选中数组
 * 返回值：最大价值
 ************************************************************************/
int CBeibao::GetMaxValue(int n,int m,int *w,int *v,int *c)
{
    int row=n+1;
    int col=m+1;

    int i,j;    //循环变量:前i个物品能够装入载重量为j的背包中

    //value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值
    int **value=new int*[row];
    for(i=0;i0;ij,第i个物品不装入背包
            value[i][j]=value[i-1][j];
            //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值
            int temp=value[i-1][j-w[i]]+v[i];
            if(w[i]<=j && temp>value[i][j])
                value[i][j]=temp;
        }
    }

    //逆推求装入的物品
    j=m;
    for(i=row-1;i>0;i--)
    {
        if(value[i][j]>value[i-1][j])
        {
            c[i]=1;
            j-=w[i];
        }
    }

    //记录最大价值
    int nMaxVlaue=value[row-1][col-1];

    //释放该二维数组
    for(i=0;iValue,m_pCount);
    m_nMaxValue=nValue;
    return nValue;
}

//显示结果
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);
}

//显示菜单
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);

            //获取满足最大载重量的最大价值
            CBeibao beibao(sfilename);
            int nMaxValue=beibao.GetMaxValue();
            if(nMaxValue)
            {
                beibao.Display(nMaxValue);
                int nlen=strlen(sfilename);
                strcpy(sfilename+nlen-4,"_result.txt");
                beibao.Display(nMaxValue,sfilename);
            }
            else
                printf("   error! please check the input data! ");
        }

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

5. 运行结果如下

文件中的内容如下：

1. input.txt
        4 10
        2 3 4 7
        1 3 5 9          

    input_result.txt
        12
        2  1
        4  1

2. input1.txt
        5 10
        2 2 6 5 4
        6 3 5 4 6

    input1_result.txt
        15
        1  1
        2  1
        5  1
                              3. input2.txt
        5 15
        2 6 4 7 9
        1 6 5 9 4

    input2_result.txt
        16
        1  1
        2  1
        4  1

4. input3.txt
        10 105
        12 16 24 7 29 32 5 43 31 1
        11 16 15 9 24 25 3 32 41 7

    input3_result.txt
        112
        1  1
        2  1
        4  1
        6  1
        7  1
        9  1
      10  1