0-1背包问题-动态规划解 xmu1028

时间：2010-08-02 来源：hbj_2008

这是一个很经典的问题，0-1背包问题。写这个程序中出现过几次很大的错误，不是算法问题，是界限问题。无意之中使程序中的运算超出定义数组的范围，导致一些莫名其妙的错误。由于没有这方面的经验，一两天看代码竟然没有发现。

还是看一本书中的代码，有效部分跟我的代码不太一样，我就思考它存在有什么作用，才明白过来。

算法，我大致描述一下：定义一个二维数组，z(n,m),其中n表示从1，2，3…n，这n个装包选择，m表示这个包的容量，z(n,m)表示在容量为m，从1到n这n个选择中，能得到的最大好处z(n,m);

其中动态规划的公式为：z(n,m) 两种可能： 1. z(n-1,m), m<p[n] , p[n]为第n个包的大小； 2. max(z[n-1][m] , z[n-1][m-p[n]]) 解释就是第一种可能第n个游戏大小要大于包的总容量，游戏n不用考虑；第2中可能就是游戏 n 小于包的容量，取 z[n-1][m]和z[n-1][m-p[n]]的最大值;

01    #include<iostream>
02    #include<cstdlib>
03    #define row 1003
04    #define coloum 8194
05    int a[row][coloum] ={0};
06    using namespace std;
07    void init(void) //初始化二维数组，其实在这题中可以去掉，不影响结果，代码更简洁

08    {
09    for(int i=0;i<row;i++)
10    for(int j=0;j<coloum;j++)
11    a[i][j]= 0 ;
12    }
13
14    void Fbag(int n, int m,int* p, int* v)
15    { //n是游戏个数，m是包的容量 ,p是游戏大小序列，v是游戏厌恶序列

16
17    int cmin = min(p[0]-2,m-1); //这个是限制游戏大小比包的总 //容量还要大，我开始就栽在这里

18    for(int j=0;j<=cmin;j++) //只有一个Game,初始化第一行

19    a[0][j]=0;
20    for(int j=p[0]-1;j<m;j++)
21    a[0][j]= max(0,v[0]);
22    for(int i=1;i<n-1;i++)
23    {
24    cmin = min(p[i]-2,m-1);
25    for(int j=0;j<=cmin;j++)
26    a[i][j]=a[i-1][j];
27    for(int j=p[i]-1;j<m;j++)
28    a[i][j]=max(a[i-1][j],a[i-1][j-p[i]]+v[i]);
29    }
30    a[n-1][m-1]=a[n-2][m-1];
31    if(p[n-1]<=m)
32    a[n-1][m-1]=max(a[n-1][m-1],a[n-1][m-1-p[n-1]]+v[n-1]);
33    }
34
35    int main()
36    {
37    int n , m ;
38    int temp ;
39    int sum ;
40    int flag =0 ;
41    cin>>n >>m ; //输入个数和包容量

42    int *p = new int[n];
43    int *x = new int[n];
44    int *v = new int[n];
45    for(int i=0;i<n;i++)
46    cin>>p[i];
47    for(int i=0;i<n;i++)
48    cin>>v[i];
49    init();
50    Fbag(n,m,p,v);
51    sum =a[n-1][m-1];
52    temp = m -1 ;
53    for(int i=n-1;i>0;i--)
54    {
55    if(a[i][temp]==a[i-1][temp]) x[i]=0;
56    else
57    {
58    x[i]=1 ;
59    temp = temp-p[i]; //我第二次在这里除了问题， //就是查找那些包被放进去，那些包没有被放进去，谨记！！！

60    sum -=v[i];
61    flag ++ ;
62    }
63    }
64    if(sum) { x[0] = 1 ; flag ++ ; }
65    else x[0] = 0;
66    cout<<flag<<endl;
67    for(int i=0;i<n;i++)
68    {
69    if(x[i]!=0) cout<<i+1<<" ";
70    }
71    cout<<endl;
72    system("pause");
73    return 0 ;
74    }