01背包

发表于 | 更新于: | 次
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

颓了一个月就学了这点东西…咸死我算了

背包问题是DP问题的分支，最近几年提高组考DP考得也不少，所以暂时先把重心放到这类问题上面

什么是背包问题呢？

就是给你一堆东西和有限的体力(或者时间)，求出能获得的最大物品价值

什么是01背包呢？

就是把物品数量换为每种只有一个啦

背包问题有如下几种分支

完全背包(物品数量无限)

多重背包(物品数量有限)

01背包(物品数量只有1个)

只要是个人都看得出来01背包是多重背包范畴，只不过物品数量只有1个

这篇博(shui)客(wen)就先从最简单的01背包开始

老规矩先贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>

using namespace std;

int tim, herb; //这里tim是从time改来的，怕关键字冲突
int dp[101][1001], v[101], w[101];//v为value，物品价值; w为weight,物品重量(所需时间)

int main()
{
    cin >> tim >> herb;
    for(int i = 1; i <= herb; i++)//写入数据
        cin >> w[i] >> v[i];
    for(int i = 1; i <= herb; i++)
    {
        for(int j = tim; j >= 0; j--)//为什么要反向循环呢？因为体力肯定是在减少的啊(
        {
            if (j >= w[i])
            {
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[herb][tim];
    return 0;
}

我们设dp [ i ] [ j ]为当体力为 j 时 选取前 i 个物品的价值总和

瞎编个数据举例子，比如我们有10点体力

物品编号：1 2 3

物品重量：5 4 6

物品价值：3 9 2

很明显，当 i = 1的时候，拿第二个物品是最值的，于是就有了dp [1] [4] = 9， 剩下6点体力

物品 1，3都可以拿

很明显我们再拿一个物品 1为最优解

其实我们也可以拿物品 3，但是那不是最好的

于是可以推出dp方程

1
dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])//是拿了这个物品，还是不拿

剩下的1点体力啥都拿不了，于是我们发现dp [3] [10] = dp[2] [9]

就可以推出当 j < w[ i ] 的时候，dp[ i ] [ j ] = dp[ i - 1] [ j ]

综上，就可以得出题目的解法了

其实还可以优化到用一维数组做，进一步降低空间复杂度

01背包的核心，就是对于每个物品有拿，不拿两种状态

我们设dp[ j ]为体力为 j 时的物品最大价值, 体力变化就隐藏为dp [ j ] = max(dp [ j - w [ i ] ] + v[ i ], dp [ j ])

设我们的体力 j = 10

对于第一个物品，我们有

dp [10] = max(dp [5] + 3, dp[10])

dp [9] = max(dp [4] + 3, dp[9])

dp [8] = max(dp [3] + 3, dp[8])

dp [7] = max(dp [2] + 3, dp[7])

dp [6] = max(dp [1] + 3, dp [6])

dp [5] = max(dp [0] + 3, dp [5])

此时dp里面为 0 0 0 0 3 3 3 3 3 3

对于第二个物品，我们有

dp[10] = max(dp [6] + 9, dp[10])

。。。。。懒得打了

dp [4] = max(dp [0] + 9, dp[4])

此时dp里就有 0 0 0 9 9 9 9 9 12 12

对于第三个物品，我们有

dp [10] = max(dp [4] + 2, dp[10])

懒得打.jpg

dp[6] = max(dp [0] + 2, dp[6])

此时dp里就有 0 0 0 9 9 9 9 9 12 12

于是当 j = 10 的时候，我们能得到最大价值为12

至于为什么不能正向推( j = 1 2 3 4 5这样)

同样以这个例子来看

dp [5] = max(dp [0] + 3, dp [5])

。。。

dp [10] = max(dp [5] + 3, dp[10])

很明显，当j = 10 的时候，又再拿了一次物品 1，就不是01背包而是完全背包了

这里贴一维代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>

using namespace std;

int tim, herb; 
int dp[1001], v[101], w[101];

int main()
{
    cin >> tim >> herb;
    for(int i = 1; i <= herb; i++)
        cin >> w[i] >> v[i];
    for(int i = 1; i <= herb; i++)
    {
        for(int j = tim; j >= 0; j--)
        {
            if (j >= w[i])
            {
                dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
            }
        }
    }
    cout << dp[tim];
    return 0;
}