牛客 Bessie's Weight Problem （01背包，空间优化）

发表于 | 更新于 | 阅读次数：

题目链接

题意

一头牛最多能吃H kg的草，这里有N堆草，每堆草一旦选择就必须吃完，求牛最多能吃多少kg的草

思路

很明显，这是一个01背包问题，然而最朴素的01背包会内存超限，所以要进行空间优化，这里采用背包九讲里提到的空间优化方式，很轻松就解决了。

1.1 题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci1，得到的 价值是 Wi。求解将哪些物品装入背包可使价值总和最大。
1.2 基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即 F[i,v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得 的最大价值。则其状态转移方程便是： F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所 以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问题，若 只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只和前 i−1 件物品相关 的问题。如果不放第 i 件物品，那么问题就转化为“前 i−1 件物品放入容量为 v 的背 包中”，价值为 F[i−1,v]；如果放第 i 件物品，那么问题就转化为“前 i−1 件物品放 入剩下的容量为 v−Ci 的背包中”，此时能获得的最大价值就是 F[i−1,v−Ci] 再加上 通过放入第 i 件物品获得的价值 Wi。 伪代码如下：
F[0,0..V ] ← 0
for i ← 1 to N
{
for v ← Ci to V
F[i,v] ←max{F[i−1,v],F[i−1,v−Ci] + Wi
}
1.3 优化空间复杂度
以上方法的时间和空间复杂度均为 O(V N)，其中时间复杂度应该已经不能再优化 了，但空间复杂度却可以优化到 O(V )。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环 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−Ci] 两个子问题递推而来，能否保证在推 F[i,v] 时（也即在第 i 次主循环中 推 F[v] 时）能够取用 F[i−1,v] 和 F[i−1,v−Ci] 的值呢？ 事实上，这要求在每次主循环中我们以 v ← V …0 的递减顺序计算 F[v]，这样才 能保证计算 F[v] 时 F[v−Ci] 保存的是状态 F[i−1,v−Ci] 的值。伪代码如下：
F[0..V ]←0
for i ← 1 to N
{
for v ← V to Ci F[v] ←max{F[v],F[v−Ci] + Wi
}
其中的 F[v] ←max{F[v],F[v−Ci] + Wi} 一句，恰就对应于我们原来的转移方程，因 为现在的 F[v−Ci] 就相当于原来的 F[i−1,v−Ci]。如果将 v 的循环顺序从上面的逆 序改成顺序的话，那么则成了 F[i,v] 由 F[i,v−Ci] 推导得到，与本题意不符。 事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象出一 个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。
def ZeroOnePack(F,C,W)
for v ← V to C
F[v] ←max(F[v],F[v−C] + W)
有了这个过程以后，01 背包问题的伪代码就可以这样写：
F[0..V ]←0
for i ← 1 to N
ZeroOnePack(F,Ci,Wi)

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
using namespace std;
int dp[55000], v[4000];
int n, W;
void solve()
{
    for (int i = 0; i <n; ++i)
    {
        for (int j = W; j >=v[i]; --j)
        {
            dp[j] = max(dp[j] , dp[j - v[i]] + v[i]);
        }
    }
}
int main()
{
    cin>>W>>n;
    for(int i=0 ; i<n ;i++)
        cin>>v[i];
    solve();
    cout<<dp[W]<<endl;
    return 0;
}

不成熟的01背包模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>//优化了空间的01背包模板
#include <iostream>
using namespace std;
int dp[10001], v[2000], w[2000];//w是花费,v是收益
int n, W;
void solve()
{
    for (int i = 0; i < n; ++i) {
        for (int j = W; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}
int main()
{
    cin >> n >> W;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    solve();
    cout << dp[W] << endl;
    return 0;
}
0%