经典算法(2)——0/1背包问题(动态规划法)

晨曦之光 发布于 2012/03/09 14:17
阅读 1K+
收藏 1
本博客( http://blog.csdn.net/livelylittlefish )贴出作者(三二一、小鱼)相关研究、学习内容所做的笔记,欢迎广大朋友指正!
                       
                       

0/1背包问题

                       
                       

 1. 问题描述

                             
                           
          给定一个载重量为m,n个物品,其重量为w i,价值为v i,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 ;i < row;i ++ )
    
{
        
for(j=1;j<col;j++)
        
{
            
//w[i]>j,第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]<=&& 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 > ;i -- )
    
{
        
if(value[i][j]>value[i-1][j])
        
{
            c[i]
=1;
            j
-=w[i];
        }

    }
                                                     
                          

4. 代码如下

                        
                       
      输入数据及输出数据均在文件中。
      输入数据格式:
            n m
            w 1 w 2 ... w n
            v1 v2 ... vn
      输出数据格式:
           maxValue
           i count            //i表示物品编号,count表示该物品被选中次数
           ...
/************************************************************************
 * 0/1背包问题求解 (visual studio 2005)
 * 给定一个载重量为m,及n个物品,其重量为wi,价值为vi,1<=i<=n
 * 要求:把物品装入背包,并使包内物品价值最大
 ***********************************************************************
*/


#include 
< stdio.h >
#include 
< stdlib.h >
#include 
< string .h >

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

    m_pValue[
]=;
    
//读入每个物品的价值
    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=;i<=m_nNumber;i++)
        m_pCount[i]
=;

    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=;i<row;i++)
        value[i]
=new int[col];

    
//初始化第0行
    for(j=;j<col;j++)
        value[
][j]=;

    
//初始化第0列
    for(i=;i<row;i++)
        value[i][
]=;

    
//计算
    for(i=1;i<row;i++)
    
{
        
for(j=1;j<col;j++)
        
{
            
//w[i]>j,第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]<=&& temp>value[i][j])
                value[i][j]
=temp;
        }

    }


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

    }


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

    
//释放该二维数组
    for(i=;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;
}


// 显示结果
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")!=)
    
{
        
if(stricmp(sinput,"i")==)
        
{
            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
                                
                                   
                   

原文链接:http://blog.csdn.net/livelylittlefish/article/details/2186206
加载中
返回顶部
顶部