题解 | 骨头收藏家

alt

题干分析

题设给予我们一个有限大小的背包，大小为V。同时给予我们n个骨头及其对应的价值与所占空间。求骨头收藏家使用该背包能够获得的最大骨头总价值。

算法思路

拆分问题：

我们首先考虑只装第一块骨头的情况：

背包大小从0~V递增的过程中不难证明当背包大小超过第一块骨头大小时将其塞入为最优策略。

接着我们尝试考虑放前两个骨头：我们只考虑第二块骨头

背包大小V不足以放下第二块骨头时直接继承只放第一块骨头的最优情况
背包大小V足以放下第二块，我们此时有两个选择：放下第二块与不放，不放的情况与只放一块骨头情况一致，放下第二块骨头则背包大小缩小为V-v[2]，此时子问题为在大小为V-v[2]大小的背包下只放第一块骨头的最优情况，这是我们先前计算过的值，能够直接读取，此值加上第二块骨头的价值后与另一种情况的总价值进行对比，保留总价值更高的选择。

拆分后我们设数组值dp[i][j]为考虑前i个骨头，在背包大小为j时最优的骨头搜集总价值。由此状态转移方程为：

$dp[i][j] = \left\{\begin{matrix} dp[i-1][j], (j < v[i]) \\ max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]),(j\ge v[i]) \end{matrix}\right.$

到此直接双循环嵌套进行实现即可。

优化空间

我们注意到整个DP过程只涉及dp[i][0...j]与dp[i-1][0...j]两组可视作一维数组的空间中，我们不妨复用一部分空间以此降低算法的空间复杂度。

方案有至少两种，一种是直接使用2个大小为V的数组交替使用，这样做的优点是实现简单不易出错，实现细节可以使用模二或者交换枢纽值两种方案实现实现。

另一种方案则更加节省，我们注意到更新状态时同一行的状态值不随计算先后顺序改变而改变，同时计算靠右的状态值时只依赖靠左的值，因此我们只使用一个大小为V的一维数组通过逆序更新的方式即可实现。

实现代码

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1011;
int w[N], v[N];

// 空间优化2
int dp[N];
int sol(int n, int c) {
    for (int i = 1; i <= n; ++i) {
        for (int j = c; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp[c];
}//*/

/* // 空间优化1
int dp[2][N];
int sol(int n, int c) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= c; ++j) {
            if (v[i] > j) dp[i % 2][j] = dp[(i - 1) % 2][j];
            else dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - v[i]] + w[i]);
        }
    }
    return dp[n % 2][c];
}//*/

/* // 基本DP
int dp[N][N];

int sol(int n, int c) {
    for (int i = 1; i <= n; ++i) { // 装前i个骨头
        for (int j = 0; j <= c; ++j) { // 共计j大小的空间
            // 第i个物品大小比总空间大，装不下
            if (v[i] > j) dp[i][j] = dp[i - 1][j];
            // 装得下，则选择不装或者装其中的最大价值
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    return dp[n][c];
}//*/

int main() {
    int T; cin >> T;
    for (int _ = 0; _ < T; ++_) {
        int n, c;
        cin >> n >> c;
        for (int i = 1; i <= n; ++i) cin >> w[i];
        for (int i = 1; i <= n; ++i) cin >> v[i];
        memset(dp, 0, sizeof(dp));
        cout << sol(n, c) << endl;
    }
    return 0;
}