一、题意

输入包含多组测试用例。
每组数据以一个整数n开始，表示每天的食物清单有n种食物。
接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。
输出最大幸福值。

二、解析

这是一到换了皮的裸完全背包问题。转化一下题意就是：
有n种物品，每种物品数量无限，每种物品的价值和体积分别为w[i]和v[i]。现在给一个体积为V的背包，要求输出最多能装入的价值量。

这里主要是复习一下完全背包问题的两种解题思路：

  • 方法一：看作DAG问题求解。
    这种方法我是根据紫薯的提示学到的，即把原问题看成是一个带边权的DAG最长路问题。每个体积作为一种状态，也就是DAG中的点，指向若干表示装了某一个物品后剩余体积的状态点。边权为装的那个物品的价值。这样原问题就变成了求DAG中的最长路问题了。然后就可以利用记忆化搜索的方法快速解决了。用时O(V*n)

  • 方法二：用递推法中的刷表法求解。
    这种方法是网上大多数人的做法。即用dp[i]表示剩余体积为i的背包中最多能装的价值量。然后就有转移方程：dp[i] = max(dp[i], dp[i-v[i]]+w[i])。用时也是O(n*V)
    注意dp数组只有一维。

三、代码

  • 方法一 
#include <iostream>
// #include <cmath>
#define max(x, y) (x)>(y)?(x):(y)
using namespace std;
const int maxn = 100 + 5, maxv = 100000 + 5;
int n, w[maxn], v[maxn], V, memo[maxv];

int dp(int V) {
    int & res = memo[v];
    if(res != -1) return res;
    res = 0;
    for(int i = 0; i < n; i ++) if(V >= v[i]) res = max(res, dp(V - v[i]) + w[i]);
    return res;
}

int main() {
    while(cin >> n) {
        for(int i = 0; i < n; i ++) cin >> w[i] >> v[i];
        cin >> V;
        fill(memo, memo + V + 1, -1);
        cout << dp(V) << endl;
    }
}
  • 方法二 
#include <iostream>
// #include <cmath>
#define max(x, y) (x)>(y)?(x):(y)
using namespace std;
const int maxn = 100 + 5, maxv = 100000 + 5;
int n, w[maxn], v[maxn], V, dp[maxv];

int main() {
    while(cin >> n) {
        for(int i = 0; i < n; i ++) cin >> w[i] >> v[i];
        cin >> V;
        fill(dp, dp + V + 1, 0);
        for(int i = 0; i < n; i ++) {
            for(int j = v[i]; j <= V; j ++) {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        cout << dp[V] << endl;
    }
}

在用递推法时，在本题中i循环和j循环的顺序关系不大，但在某些题目情境下，需要特别注意顺序问题，比如 这道题目（ https://blog.nowcoder.net/n/8c089bfcadc9477f8ba3be50088838ed ）中，需要求的是种数，则必须i循环在外。并且在这种题目下，也没有办法使用DAG的方法解决了，只能使用刷表法。

四、归纳

  • 完全背包问题：即将n种物品放入容量为V的背包中， 每种物品有无限个。
    • 可以转化为DAG最长路问题求解，也可以用刷表法解决。
    • 转移方程： dp[i] = max(dp[i], dp[i-v[i]]+w[i])
    • dp[i]表示剩余体积为i的背包中最多能装的价值量