source:abc221g
有 \(n\) 个物品，体积分别为 \(a_{1,2,\dots,n}\) ，要求从中选出若干个物品使得体积和为 \(V\) 。令 \(A=\max a_i\) ，\(V\le nA\) 。一般的 01 背包做法是 \(O(n^2A)\) 的，但存在一种相对简单的做法可以做到复杂度 \(O(nA)\) 。下面描述这个做法。
首先任意排列这个物品序列 \(a\) ，然后暴力从前往后取，直到当前取到的体积和 \(\ge V\) （如果取不到则显然无解）。
然后这些物品被分为两类，第一类是被选中的，第二类是没有被选中的，如果存在一个合法方案，那么肯定是从第一类中去掉若干个物品，再加入第二类中的若干个物品。
为了减小值域，有一个非常直觉的做法：如果当前的体积和 \(\gt V\) 就考虑一个删除操作，否则就考虑加入操作。这个做法显然是对的，并且把 dp 的值域从 \(O(nA)\) 降到了 \(O(A)\) （注意实际实现与描述略有不同）。考虑 dp ，可以令 \(f_{l,r,w}\) 表示：已经确定区间 \([l,r]\) 的方案，区间之外左边全都被选择，右边全都不被选择，是否存在一种方案满足体积和为 \(w\) 。转移类似区间 dp，从 \(f_{t+1,t}\) 开始逐步向左向右扩展，其中 \(t\) 是一开始选的物品数量。不过这样 dp 的复杂度还是 \(O(n^2A)\) 的。
注意到 dp 数组的内容相对简单（只有 01），因此考虑变更一下 dp 方式，令 \(g_{r,w}\) 表示最大的一个 \(l\) 满足 \(f_{l,r,w}=1\) ，同样是可以转移的，分为三类：
-
\(g_{r,w}\leftarrow g_{r-1,w}\) ，对应最右边的元素不选的情况
-
\(g_{r,w+a_r}\leftarrow g_{r-1,w}\) ，对应最右边的元素要选的情况
-
对于所有 \(l\) 满足 \(l \lt g_{r,w}\) ：\(g_{r,w-a_l}\leftarrow l\) ，也就是向左扩展
这三类转移做的都是取 \(\max\) 操作。
前两个转移的复杂度是 \(O(nA)\) 的。考虑第三个转移，由于需要枚举 \(l\) 所以复杂度仍然是 \(O(n^2A)\) 。事实上还可以做一步优化，发现所有 \(l\lt g_{r-1,w}\) 的 \(l\) 都是没有用的，因为完全可以先从 \(f_{*,r-1,w}\) 转移到 \(f_{l,r-1,w-a_l}\) 然后再向右扩展，所以实际上只需要枚举 \(l\in[g_{r-1,w}, g_{r,w})\) 。这样的话对于某个特定的 \(w\) 容易得出枚举 \(l\) 的总数是 \(O(n)\) 的，因此总复杂度被优化到 \(O(nA)\) 。
注意转移顺序。
放一个代码，这份代码可以输出方案。
#include<bits/stdc++.h>
using namespace std;
bool dp(int n, int A, int V, vector<int> a, vector<bool> &res){
if(V==0){
res.resize(n);
fill(res.begin(), res.end(), 0);
return true;
}
int sum=0, t=0;
while(t<n && sum<V){
sum+= a[t];
t++;
}
if(sum<V){
return false;
}
int D=A-V;
vector<vector<int>> f(n, vector<int>(A*2+1, -1)), lst(n, vector<int>(A*2+1));
auto upd=[&](int pi,int pj,int val,int info){
if(val>f[pi][pj]){
f[pi][pj]=val;
lst[pi][pj]=info;
}
};
f[t-1][sum+D]=t;
for(int r=t-1; r<n; r++){
if(r>=t){
for(int w=0; w<=A*2; w++){
upd(r, w, f[r-1][w], 0);
}
for(int w=0; w<=A*2-a[r]; w++){
upd(r, w+a[r], f[r-1][w], 1);
}
}
for(int w=A*2; w>=0; w--){
for(int l=(r==0 || f[r-1][w]==-1? 0: f[r-1][w]); l<f[r][w]; l++){
if(w>=a[l]){
upd(r, w-a[l], l, 2);
}
}
}
}
if(f[n-1][V+D]==-1){
return false;
}
res.resize(n);
fill(res.begin(), res.begin()+t, 1);
fill(res.begin()+t, res.end(), 0);
int ci=n-1, cj=V+D;
while(!(ci==t-1 && cj==sum+D)){
int op=lst[ci][cj];
if(op==0){
ci--;
}
else if(op==1){
res[ci]=1;
cj-= a[ci];
ci--;
}
else{
res[ f[ci][cj] ]=0;
cj+= a[ f[ci][cj] ];
}
}
return true;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,V; cin>>n>>V;
vector<int> a(n);
for(auto &x:a){
cin>>x;
}
vector<bool> res;
bool ans=dp(n, *max_element(a.begin(), a.end()), V, a, res);
cout<< ans <<'\n';
if(ans){
for(auto x:res){
cout<<x<<' ';
}
cout<<'\n';
}
}