文档介绍：动态规划
by 石门中学柯新宇
背包问题简单类型
01背包--即选和不选 O(n)
完全背包--有无限个物品,倒着做就行了,O(n)
至于为什么? ---------自已YY
多重背包--枚举个数 O(nmW)
背包问题简单类型
01背包--即选和不选 O(n)
完全背包--有无限个物品,倒着做就行了,O(n)
至于为什么? ---------自已YY
多重背包--枚举个数 O(nmW)
对于多重背包,有这样一个问题:
有n种物品,它们重量和价值为 wi 和 vi。选出一些物品,使总重量不超过 W 且它们的价值最大。
第 i 种物品可以选 mi 个
n≤100 wi,vi≤100 mi,W≤10000
显然,直接做是肯定超时的
关于多重背包的优化
分解优化:
对于 mi 来说
mi 可以分解成1+2+……+2^k+a( 0 ≤ a < 2^(k-1) )
那么这就包含了所有的情况( 0 ~ mi )
一个选 mi 个的物品就分成 log mi 个物品(只选一个)
这样,总物品就分成了O(nlogm) 个。
直接一般的01背包就可以在O(nW logm) 内A掉。
关于多重背包的优化
int dp[maxw+1];
void solve()
{
for(int i=0;i<=n;i++){
int num=m[i];
for(int k=1;num>0;k<<=1){
int mul=min(k,num);
for(int j=W;j>=w[i]*mul;j--){
dp[j]=max(dp[j],dp[j-w[i]*mul]+v[i]*mul);
}
num-=mul;
}
}
printf("%d\n",dp[W]);
}
拆分物品:
还有一个更吊的优化----------O(nW)
关于多重背包的优化
从简单的出发:
dp[ i ][ j ]=到第 i 个物品,选了重量不超过 j 的最大价值
dp[ i ][ j ]=max { dp[ i-1 ][ j-k*w[ i ] ]+k*v[ i ] } --条件略
我们可以观察到,根据 j mod w[ i ] 的值不同,可以分为w[i] 组,( 每一组的情况都是一样的)
这是显然的,不用证明
关于多重背包的优化
我们先考虑 j mod w[ i ] =0 的情况
定义:
a[ j ]=dp[ i ][ j * w[ i ] ]
那么 dp[ i ][ (j+k)*w[ i ] ]=
max { a[ j ]+k*v[ i ] , a[ j+1 ]+(k-1)*v[ i ] , ……, a[ j+k ] }
似乎发现了什么??
关于多重背包的优化
我们先考虑 j mod w[ i ] =0 的情况
定义:
a[ j ]=dp[ i ][ j * w[ i ] ]
那么 dp[ i ][ (j+k)*w[ i ] ]=
max { a[ j ]+k*v[ i ] , a[ j+1 ]+(k-1)*v[ i ] , ……, a[ j+k ] }
似乎发现了什么??
定义 b[ j ]=a[ j ]-j*v[ i ]
那么 dp[ i ][ (j+k)*w[ i ] ]=
max { b[ j ] , b[ j+1 ] , ……, b[ j+k ] }+( j+k )*v[ i ]
dp[ i ][ (j+k)*w[ i ] ]=
max { b[ j ] , b[ j+1 ] , ……, b[ j+k ] }+( j+k )*v[ i ]
求b[ j~j+k ]的最大值,用队列优化就行了
int n,W,w[maxn],v[maxn],m[maxn],dp[maxw+1]; //dp数组,循环使用
int dep[maxw+1]; //双端队列下标
int depv[maxw+1]; //双端队列保存值
void solve() {
for(int i=0;i<n;i++) {
for(int a=0;a<w[i];a++) {
int s=0,t=0;
for(int j=0;j*w[i]+a<=W;j++) {
int val=dp[j*w[i]+a]-j*v[i];
while(s<t && depv[t-1]<=val) t--;
dep[t]=j; depv[t++]=val; //加入j
dp[j*w[i]+a]=depv[s]+j*v[i];
if(dep[s]==j-m[i]) s++; //退掉无用的值
}
}
}
printf("%d\n",dp[W]);
}
隐藏在DP之中的数学
bzoj3622
[ 题目大意]
有 n 个 A[