0-1背包问题

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

相信很多人拿到这道题的时候，立马想到是不是用贪心去做，其实不是的。这道题，我们可以用GAD的动态规划来求解。那这样的话找到动态转移方程就成了解决此题的关键。我们来看看一组图片：

如果你能将这个图自己想清楚，那0-1背包问题你也就弄得很明白了。

从下往上依次执行 D（i，j）= max（D（i+1，j）D（i+1,j-w[i]）+value[i]）

首先：重量为5的物品在背包容量为8的情况下只能是价值为6；

其次：我们发现，如果把重量为4的物品拿进来，我们任然无法增加价值，因为背包的容量不够了；

再者：又把重量为3的物品拿来，发现，当背包容量为8的时候，可以放3和5物品，更新8容量的价值为8；

最后：最后看重量为2的物品，结果它还可以放2和5价值更大。

因此可以很容易的就推导出它的状态转移方程。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int maxn = 101;
unsigned int d[maxn][maxn];
using namespace std;
struct node
{
    int value;
    int weight;
}th[maxn];

int main()
{
    int n, m;
    while (cin>>n && n)
    {
        cin >> m;//物品的个数
        memset(d, 0, sizeof(d));
        for (int i = 1; i <= n; i++)//每个物品的重量和价值
            scanf("%d %d", &th[i].weight, &th[i].value);
        //正三角；
        for (int i = n; i >= 1; i--)
        {
            for (int j = 1; j <= m; j++)
                if (j >= th[i].weight)
                    d[i][j] = max(d[i+1][j], d[i + 1][j - th[i].weight] + th[i].value);// d[i + 1][j - th[i].weight]确保了不会超过背包的最大承重，同时为下一个物品腾出位置来存放
                else
                    d[i][j] = d[i + 1][j];
        }
        printf("%d
", d[1][m]);//最终输出；
    }
    return 0;
}

View Code

上面这个代码用的是正三角的形式，其实还有它的对称的形式。它的状态转移方程为：D[i][j] = max(D[i - 1][j], D[i - 1][j - th[i].weight] + th[i].value)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int maxn = 101;
unsigned int d[maxn][maxn];
using namespace std;
struct node
{
    int value;
    int weight;
}th[maxn];

int main()
{
    int n, m;
    while (cin>>n && n)
    {
        cin >> m;
        memset(d, 0, sizeof(d))；
        //倒三角；
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d", &th[i].weight, &th[i].value);//书上数只有这种可以边输入边执行，但是我试了一下正三角的也可以。不过还是老老实实的好。
            for (int j = 1; j <= m; j++)
                if (j >= th[i].weight)
                    d[i][j] = max(d[i - 1][j], d[i - 1][j - th[i].weight] + th[i].value);//d[i-1][j-th[i].weight]保证了不超过背包的最大承重；
                else
                    d[i][j] = d[i - 1][j];
        }
        printf("%d
", d[n][m]);
    }
    return 0;
}

View Code

除此之外，这里还可以更加的简便。可以只用以为的数组——滚动数组。

memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++)
{
    scanf("%d %d", &th[i].weight, &th[i].value);
    for (int j = m; j >= 1; j--)
        if (j >= th[i].weight)
            f[j] = max(f[j], f[j - th[i].weight] + th[i].value);
}
printf("%d
", f[m]);

View Code

那你不经就想问了，为什么可以这样呢？我们之前的得到每一个不同的物品时，新的价值都是从上一个物品的价值上得到的，而我们在得到新的值得时候，做几步复制的操作，也就是没有改变原价值的大小，只是最后判断的时候，比较原有价值和可能的最大价值（这个价值也又原价值数组中的某个数加上该物品价值得到的），所以做的而言，起作用的只是上一个原有价值而已，打在处理的时候，我们要考虑，执行先后的问题，不然更新得情况会有错误。j需要逆序枚举。

例题：饭卡 Cow Ehibition