题意
有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包,每种物品有无数多个。
记第 $i$ 中物品最终在背包里放了 $a_i$ 个,我们需要这个答案序列先单调非降再单调非升,即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。
对于每一个背包容量 $1,2,3,\dots,m$,在使得背包能够装下最大价值总和的物品的情况下,求一个最小的 $k$ 以及对应的最大价值总和。
$1\le n \le 2000,1\le m \le 500$
解析
我们先考虑 easy version,即 $k$ 是给定的值的情况。
我们发现可以把所有物品拆解为 $1\sim k,2\sim k,\dots k\sim k,1\sim k+1,2\sim k+1\dots 1\sim n,2\sim n\dots k\sim n$ 这么多物品,我们用这些物品跑完全背包,结果显然是符合要求的。看似时间复杂度为 $O(n^2m)$,但是由于体积不为零,所以超过 $500$ 个数量的物品是无效的,实际时间复杂度为 $O(nm^2)$。
然后再回到 hard version,我们发现对于相邻的两个数作为 $k$,他们的物品重合度是很高的,所以我们考虑有没有方法可以减少更新次数。记 $f_{i,j}$ 为以 $i$ 点为 $k$,体积为 $j$ 的最大价值,有一个很神奇的式子 $f_{i,j}=\max{f_{i,j},f_{i+1,j},f_{i,j-W}+V}$,再更新过程中,我们先从左往右枚举 $i$ 作为左端点,再从右往左枚举 $j$ 更新 $f_{j,x}$,更新的是 $i \sim j$ 的所有物品组成的一个复合物品,这部分代码如下:
for(int i=1;i<=n;i++){
for(int j=n;j>=i;j--){
ll W=w[j]-w[i-1];//此处为前缀和
ll V=v[j]-v[i-1];//此处为前缀和
for(int k=W;k<=m;k++){
f[j][k]=max({f[j][k],f[j+1][k],f[j][k-W]+V});
}
}
for(int j=1;j<=m;j++){
if(f[i][j]>ans[j]){
ans[j]=f[i][j];
ansid[j]=i;
}
}
}
你发现,对于 $f_{j,k}$,以这样的遍历方式,必然有 $f_{j+1,k}$ 中考虑过的数都在 $f_{j,k}$ 的考虑范围内。但这一式子真的不会有疏漏吗?其实是有的,但是无所谓,原因是这样的:
假设我们遍历到 $i,j$,则 $f_{j,k}$ 考虑到了 $1\sim j,2\sim j,\dots i-1\sim j$ 这些物品,而这些物品是不被包含在 $f_{j+1,k}$ 中的。那么,假设最优解是选取了若干个上述物品,又选取了 $i\sim j+1$ 这个物品,这种情况是考虑不到的。但我们发现,物品 $i\sim j+1$ 与前述物品的任意数量的组合都可以变成以下两种中的一种:
- 若干个 $x \sim j$ 与若干个 $x\sim j+1$ 与若干个 $i \sim j$ 的组合,这是可以由 $f_{i,j}$ 以及 $f_{i,j-W}+V$ 更新出来的。(其中的 $x$ 小于 $i$)
- 若干个 $i \sim j+1$ 与若干个 $x\sim j+1$ 与若干个 $i \sim j$ 的组合,这是可以由 $f_{i+1,j}$ 以及 $f_{i,j-W}+V$ 更新出来的。(其中的 $x$ 小于 $i$)
你可以通过画图观察这些块的重合关系来发现这一点。这也是我们阅读出题者题解时最大的疑惑,在此略加解释。
代码
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=2e3+5;
const int NN=2e6+5;
const int M=505;
ll f[N][M],ans[N],ansid[N];
int n,m;
ll w[N],v[N],wb[NN],vb[NN];
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d",&w[i],&v[i]);
w[i]+=w[i-1];
v[i]+=v[i-1];
ansid[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=n;j>=i;j--){
ll W=w[j]-w[i-1];
ll V=v[j]-v[i-1];
for(int k=W;k<=m;k++){
f[j][k]=max({f[j][k],f[j+1][k],f[j][k-W]+V});
}
}
for(int j=1;j<=m;j++){
if(f[i][j]>ans[j]){
ans[j]=f[i][j];
ansid[j]=i;
}
}
}
for(int i=1;i<=m;i++) printf("%lld ",ans[i]);
printf("\n");
for(int i=1;i<=m;i++) printf("%lld ",ansid[i]);
return 0;
}