给定背包容量 m ,物品种数 n ,每个物品的体积
a
i
a_{i}
ai ,价值
b
i
b_{i}
bi ,个数
c
i
c_{i}
ci。
求背包能装下的最大价值和,且输出任意可行方案。
这是经典的多重背包问题,可以有多种解法。
-
01背包解法
按每种物品的个数 c i c_{i} ci 将物品拆成 c i c_{i} ci 个物品然后做全部拆完后的物品的 01 背包,很明显复杂度是 O ( n m ∑ c i ) O(nm\sum{c_{i}}) O(nm∑ci) 的。
先解释以下输出方案的问题:以二维数组来计算,在计算完后,找到第 n 个物品最大价值的位置 f [ n ] [ p ] f[n][p] f[n][p] ,此时比较它和 f [ n − 1 ] [ p ] f[n-1][p] f[n−1][p] 的值,若是不相等则说明在当前容量时取了第 n 个物品,输出然后减去容量即可,依次类推。
记得不要拿超过 c i c_{i} ci 次 i 物品。
code
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include
#include #include #include #include #include #include #include #include using namespace std; using ll=long long; using P=pair<int,int>; const ll inf=1e18; void solve() { int n,m; cin>>n>>m; vector<int>a(n+1),b(n+1),c(n+1); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=n;i++)cin>>c[i]; vector<vector<int>>f(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++) { f[i]=f[i-1]; for(int j=1;j<=c[i];j++) { for(int k=m;k>=a[i];k--) { f[i][k]=max(f[i][k],f[i][k-a[i]]+b[i]); } } } int p=max_element(f[n].begin(),f[n].end())-f[n].begin(); cout<<f[n][p]<<"\n"; for(int i=n;i>=1;i--) { while(f[i][p]>f[i-1][p]&&c[i]) { cout<<i<<" "; p-=a[i],c[i]--; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--)solve(); return 0; } -
二进制拆分法
从1 可知,对每个物品循环多次的目的是将其转化为 c i c_{i} ci 物品,可以采用将每个物品的循环次数按二进制位去拆分,将其表达成 2 0 , 2 1 . . . 2 k , m − ∑ i = 0 k 2 i 2^0,2^1...2^k,m-\sum_{i=0}^{k}2^i 20,21...2k,m−∑i=0k2i, 一共有 log 个物品,从 1 到 c i c_{i} ci 的物品个数均可以通过使用其中的某一子集拼凑而成,因此只需要将第 i 个物品拆成 log 个物品去按方法一的方式计算即可。
总复杂度是 O ( n m ∑ l o g ( c i ) ) O(nm\sum{log(c_{i})}) O(nm∑log(ci)) 。
code
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include
#include #include #include #include #include #include #include #include using namespace std; using ll=long long; using P=pair<int,int>; const ll inf=1e18; void solve() { int n,m; cin>>n>>m; vector<int>a(n+1),b(n+1),c(n+1); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=n;i++)cin>>c[i]; vector<vector<int>>f(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++) { f[i]=f[i-1]; int p=c[i]; for(int j=1;j<=p;p-=j,j<<=1) { for(int k=m;k>=j*a[i];k--) { f[i][k]=max(f[i][k],f[i][k-j*a[i]]+j*b[i]); } } if(p) { for(int k=m;k>=p*a[i];k--) { f[i][k]=max(f[i][k],f[i][k-p*a[i]]+p*b[i]); } } } int p=max_element(f[n].begin(),f[n].end())-f[n].begin(); cout<<f[n][p]<<"\n"; for(int i=n;i>=1;i--) { while(f[i][p]>f[i-1][p]&&c[i]) { cout<<i<<" "; p-=a[i],c[i]--; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--)solve(); return 0; } -
单调队列优化
考虑当前枚举的是物品i,对于容量j而言,可以继承的只有 j − a i , j − 2 a i . . . j − x ∗ a i ( x < = c i & & j − x ∗ a i > = 0 ) j-a_{i},j-2a_{i}...j-x*a_{i}(x<=c_{i}\&\&j-x*a_{i}>=0) j−ai,j−2ai...j−x∗ai(x<=ci&&j−x∗ai>=0),也就是说对于在模 a i a_{i} ai 的余数集下,不同余数集间互不干扰,因此可以将余数集进行分开枚举。
对于同一个余数集, f [ i ] [ j ] = m a x { f [ i − 1 ] [ j − x ∗ a i ] + x ∗ b i } , x < = c i f[i][j]=max\{f[i-1][j-x*a_{i}]+x*b_{i}\},x<=c_{i} f[i][j]=max{f[i−1][j−x∗ai]+x∗bi},x<=ci ,可以使用单调队列来维护,在每次计算出 f [ i ] [ j ] f[i][j] f[i][j] 之后,将向队列中插入 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] ,在插入前需要判断当前尾端的数据 f [ i − 1 ] [ k ] + ( j − k ) / a i ∗ b i ( j % a i = = k % a i ) f[i-1][k]+(j-k)/a_{i}*b_{i}(j\%a_{i}==k\%a_{i}) f[i−1][k]+(j−k)/ai∗bi(j%ai==k%ai) 是否比 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] 更大,若不是,则 f [ i − 1 ] [ k ] f[i-1][k] f[i−1][k] 这个点并不比 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] 优,因此可以从尾端d出队列。
对以上 *** 作多次执行,直到尾端的点比当前点优,才插入加入当前点。
这样 *** 作下来队列内的点是逐渐递减的(并不指数值大小逐渐递减,而是对于容量 j 时,满足 f [ i − 1 ] [ x ] + ( j − x ) / a i ∗ b i > = f [ i − 1 ] [ y ] + ( j − y ) / a i ∗ b i f[i-1][x]+(j-x)/a_{i}*b_{i}>=f[i-1][y]+(j-y)/a_{i}*b_{i} f[i−1][x]+(j−x)/ai∗bi>=f[i−1][y]+(j−y)/ai∗bi ,其中 x < y x
x<y )。因此每个 f [ i ] [ j ] f[i][j] f[i][j] 的答案即为队首 f [ i − 1 ] [ t o p ] + ( j − t o p ) / a i ∗ b i f[i-1][top]+(j-top)/a_{i}*b_{i} f[i−1][top]+(j−top)/ai∗bi。
需要在每次取队首为答案前,对队首与当前容量 j 的值进行判定,若是超过限制个数范围则需从队首d出,直到满足情况,则队首就是答案。
以上队列为双端队列,首尾均可进行d出插入 *** 作。
对于空间可以将物品这一维优化掉,每次求前只需要用 g = f g=f g=f 保存上一次结果,然后在 g 的基础上更新 f 即可。
考虑最后的单调队列的优化,对于每个物品会分为多个余数集,但所有的容积就只会被计算一次,而且对于每个物品的入队出队的情况而言,只会最多插入 m 次,d出 m 次。
取最大值则是的 O ( 1 ) O(1) O(1)。
则总的复杂度为 O ( n m ) O(nm) O(nm)。
code#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include
#include #include #include #include #include #include #include #include using namespace std; using ll=long long; using P=pair<int,int>; const ll inf=1e18; void solve() { int n,m; cin>>n>>m; vector<int>a(n+1),b(n+1),c(n+1); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=n;i++)cin>>c[i]; vector<vector<int>>f(n+1,vector<int>(m+1)); for(int i=1;i<=n;i++) { f[i]=f[i-1]; for(int j=0;j<a[i];j++) { deque<int>dq; for(int k=j;k<=m;k+=a[i]) { while(dq.size()&&(k-dq.front())/a[i]>c[i]) { dq.pop_front(); } if(dq.size()) { f[i][k]=max(f[i][k],f[i-1][dq.front()]+(k-dq.front())/a[i]*b[i]); } while(dq.size()&&f[i-1][dq.back()]+(k-dq.back())/a[i]*b[i]<f[i-1][k]) { dq.pop_back(); } dq.push_back(k); } } } int p=max_element(f[n].begin(),f[n].end())-f[n].begin(); cout<<f[n][p]<<"\n"; for(int i=n;i>=1;i--) { while(f[i][p]>f[i-1][p]&&c[i]) { cout<<i<<" "; p-=a[i],c[i]--; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while(t--)solve(); return 0; } 以上代码未经验证,不能保证正确率。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)