【动态规划】背包问题----01背包

题目描述

acwing 01背包

要点

1.每件物品只能使用一次
2.总体积不超过V
3.总价值最大

分析

按照集合划分

最后一个不选 i
代表要从 1 到 i - 1 中选择物品，并且其体积不超过j，这其实就是f[i - 1][j]
最后一个选 i
如果要选i的话，我们可以这么考虑，我们先把i的这个空给空出来，那么剩下的内容就变成从1到i - 1的物品中选择物品，并且其体积不超过 j - vi(这样就是把这个i的空空出来），其总价值的最大值为f[i - 1][j - v[i]],再把i的价值加上，就得到了最后一个选i这一类的最大值f[i - 1][j - v[i]] + w[i]

所以f[i, j] = max (f[i - 1][j],f[i - 1][j - v[i]]) + w[i]

二维写法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[N]; //体积
int w[N]; //价值
int f[N][N]; //f[i][j]，j体积下前i个物品的最大价值

int main()
{
    int n, m;
    scanf ("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++) scanf ("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++)
        {
            if (j < v[i]) 
                f[i][j] = f[i - 1][j];
            else 
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }

    printf ("%d\n", f[n][m]);

    return 0;
}

在上面的代码里我们可以看到

f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);

这里，推导f[i][j]的时候，我们只用到了f[i - 1]这一层的信息，所以我们可以使用滚动数组将需要用到的信息存到一维数组中。所谓滚动数组，其实也就是我计算第 i 层的数据时，使用滚动数组的内容（就是i - 1层的数据），当我计算完之后，我的数据就存进滚动数组中，这样计算 i + 1 层的时候，就可以继续使用第 i 层的数据。

【重点】由于要使用上一层的数据故需逆序

一维写法

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int v[N], w[N]; 
int f[N]; 

int main()
{
    int n, m;
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf ("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    printf ("%d\n", f[m]);

    return 0;
}