POJ3624 0-1 背包问题

时间:2021-07-01 04:29:20

问题描述

  • 假设我们有n件物品,分别编号为1,
    2…n。其中编号为i的物品价值为vi,它的重量为wi。为了简化问题,假定价值和重量都是整数值。现在,假设我们有一个背包,它能够承载的重量是W。现在,我们希望往包里装这些物品,使得包里装的物品价值最大化,那么我们该如何来选择装的东西呢?

递推公式证明:

  • 我们需要选择n个元素中的若干个来形成最优解,假定为k个。那么对于这k个元素a1, a2,
    …ak来说,它们组成的物品组合必然满足总重量<=背包重量限制,而且它们的价值必然是最大的。因为它们是我们假定的最优选择嘛,肯定价值应该是最大的。假定ak是我们按照前面顺序放入的最后一个物品。它的重量为wk,它的价值为vk。既然我们前面选择的这k个元素构成了最优选择,如果我们把这个ak物品拿走,对应于k-1个物品来说,它们所涵盖的重量范围为0-(W-wk)。假定W为背包允许承重的量。假定最终的价值是V,剩下的物品所构成的价值为V-vk。这剩下的k-1个元素是不是构成了一个这种W-wk的最优解呢?

    我们可以用反证法来推导。假定拿走ak这个物品后,剩下的这些物品没有构成W-wk重量范围的最佳价值选择。那么我们肯定有另外k-1个元素,他们在W-wk重量范围内构成的价值更大。如果这样的话,我们用这k-1个物品再加上第k个,他们构成的最终W重量范围内的价值就是最优的。这岂不是和我们前面假设的k个元素构成最佳矛盾了吗?所以我们可以肯定,在这k个元素里拿掉最后那个元素,前面剩下的元素依然构成一个最佳解。

POJ3624 0-1 背包问题

POJ3624 按以上思路写出代码如下:

/* POJ 3624 .0-1背包问题 * * */
#include <iostream>
#include <cstring>
using namespace std;

int N,M;

int W[3500],D[3500];
int MaxValue[100][12890]; //MaxValue(i,j) 表示总最大负重j的情况下,取前i个物品取法所算得的最大价值

int main()
{
    memset(MaxValue,0,sizeof(MaxValue));
    cin >> N >> M;
    for(int i = 1; i <= N; ++i)
    {
        cin >> W[i] >> D[i];
        MaxValue[i][0] = 0;
    }

    for( int w = 1; w <= M; w++)
    {
        for(int i = 1; i<= N;i ++)
        {
            MaxValue[i][w] = MaxValue[i-1][w];
            if(W[i] <= w)
            {
                MaxValue[i][w] = MaxValue[i-1][w] > (MaxValue[i-1][w-W[i]]+D[i]) ? 
                                MaxValue[i-1][w] : (MaxValue[i-1][w-W[i]]+D[i]);
            }
        }
    }
    cout << MaxValue[N][M];
    return 0;
}

这时,我们还会遇到一个问题,这样提交是会超内存的。
方法可以采用:
1. 滚动数组
2. 采用一维数组

在方法1中,我们每次更新背包的二维数组,有一部分数据不再使用,是可以丢弃的。
方法2,我们发现其实可以是用一个一维数组搞定这个问题的,Bag[k] 表示 在最大负重k下,所有取法的最优价值。
先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。
下面是方法2的代码:

#include <iostream>
#include <cstring>
using namespace std;

int N,M;

int W[3500],D[3500];
int Bag[12890];

int main()
{
    memset(Bag,0,sizeof(Bag));
    cin >> N >> M;
    for(int i = 1; i <= N; ++i)
        cin >> W[i] >> D[i];
    for(int i = 1; i <= N; ++i)
    {
        for(int w = M; w >= W[i]; w--)      
        {
            if(Bag[w-W[i]] + D[i] >= Bag[w])
                Bag[w] = Bag[w-W[i]] + D[i];
        }
    }
    cout << Bag[M] << endl;
    return 0;
}