题目描述

难度分:$2018$

输入$n(1 \leq n \leq 3000)$、$m(1 \leq m \leq 3000)$表示有$n$种物品，以及一个容量为$m$的背包。

然后输入$n$行，每行输入第$i$种物品的体积$w(1 \leq w \leq m)$和价值$v(1 \leq v \leq 10^9)$。

每种物品都有无限个。为了避免选择过多相同类型的物品，有如下规定：

• 如果同一种物品选了$k$个，那么这$k$个物品的实际总价值不是$k \times v$，而是$k \times v - k^2$。

输出所选物品的价值总和的最大值。物品的体积之和不能超过$m$。

输入样例$1$

2 10
3 4
3 2

输出样例$1$

5

输入样例$2$

3 6
1 4
2 3
2 7

输出样例$2$

14

输入样例$3$

1 10
1 7

输出样例$3$

12

算法

动态规划

本质上还是个完全背包问题，因此循环的顺序还是一样的。我们将相同体积的价值放入映射$vec$，它表示“体积$\rightarrow$价值数组”。

状态定义

$dp[j]$表示所选物品的体积为$j$的情况下能够获得的最大价值，在这个定义下，答案就是$max_{j \in [0,W]}dp[j]$。

状态转移

初始情况下$dp[0]=0$。对于一般情况，分别考虑每种体积，遍历$w \in [1,W]$，看体积为$w$的物品选多少个$k$。根据完全背包套路，外层循环倒序遍历$j \in [0,W]$，内层循环正序遍历$k$，需要满足$k \times w \leq W$不能超过背包容量。状态值转移方程为$dp[j]=max(dp[j],d[j-k \times w]+happiness[k])$，$happiness[k]$表示选$k$个体积为$w$的物品可以得到的最大价值。

考虑怎么预处理出$happiness$数组，对于价值$v$，如果选一个这样的物品，价值为$v-1$。当选择的数量增加，增量即为$k \times v-k^2-((k-1) \times v-(k-1)^2)=v-2 \times k + 1$。所以$k=1$时自增为$v-1$，$k=2$时增量为$v-3$，$k=3$时增量为$v-5$，……，因此每选一个体积为$w$的物品，下次再选它，价值增量就会变为$v-2$。初始化$happiness[0]=0$，用一个大根堆$heap$来预处理出$happiness$数组，在$k \times v \leq W$的限制下遍历$k$，$happiness[k]=happiness[k-1]+v$，（其中$v$为大根堆的堆顶，初始情况下存的是$vec[w]$中所有价值的增量$v-1$，也就是$k=1$时的增量），弹出堆顶之后再压入$v-2$到$heap$中。

复杂度分析

时间复杂度

外层循环遍历$w \in [1,W]$的时间复杂度为$O(W)$，内部要先处理$happiness$，根据调和级数，这部分的时间复杂度为$O(WlnW)$。预处理之后还要进行完全背包，需要遍历$j \in [0,W]$，对于每个$j$，又要遍历满足$k \times w \leq W$的$k$，根据调和级数这部分的时间复杂度为$O(W^2lnW)$。因此，整个算法的时间复杂度为$O(W^2lnW)$。

空间复杂度

$vec$中存了所有$O(n)$个物品的$w$和$v$，空间复杂度为$O(n)$。而动态规划时所需要的DP数组$dp$以及$happiness$数组的空间复杂度都是$O(W)$（$w=1$，$k$可以是$W$）。因此，整个算法的额外空间复杂度为$O(n+W)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 3001;
int n, W;
vector<int> vec[N];
LL dp[N], happiness[N];

int main() {
    scanf("%d%d", &n, &W);
    for(int i = 1; i <= n; i++) {
        int w, v;
        scanf("%d%d", &w, &v);
        vec[w].push_back(v - 1);
    }
    for(int i = 0; i <= W; i++) {
        dp[i] = -1e18;
    }
    dp[0] = 0;
    LL ans = 0;
    for(int w = 1; w <= W; w++) {
        if(vec[w].empty()) continue;
        priority_queue<int> heap;
        for(int v: vec[w]) {
            heap.push(v);
        }
        happiness[0] = 0;
        for(LL k = 1; k*w <= W; k++) {
            int v = heap.top();
            heap.pop();
            happiness[k] = happiness[k - 1] + v;
            heap.push(v - 2);
        }
        for(int j = W; j >= 0; j--) {
            for(LL k = 0; k * w <= j; k++) {
                dp[j] = max(dp[j], dp[j - k*w] + happiness[k]);
            }
            ans = max(ans, dp[j]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}