初学DP(4) – 多重背包及其优化 – Codevs 3269

多重背包 我们曾经说过完全背包和01背包,但是这两个方法都有一个问题,就是物件个数都是一致的并且是确定的,但如果他不确定呢? 我们可以定义一个k循环来模拟他的件数,不过显然这样做的华时间复杂度会超过我们的想象 所以我们需要进行优化,优化的方式有两种

  • 二进制优化
  • 单调队列

二进制优化


我们来观察下面这几个数字 十进制 1 2 4 8 二进制 1 10 100 100 我们可以发现这几个数每次乘二,并且可以凑成从 1 到 1+2+4+8=15 的所有情况 至于是什么原因可以观察一下二进制数 1+10=11(3) 1-3凑齐 11+1=100(4) 1-3,4,5-7凑齐 没错每个为2^n的数,它的二进制中,第一位是1,后面全是0,这样一来我们只需要把是2^n次放并且和小于个数的数求出来,之后按个数相乘成为一个新的物品

单调队列


是否还记得队列呢? 单调队列也是队列,所谓的单调,就是指按队列中的顺序 是固定的,也就是指最优解永远放在最前面,但是问题来了,阶段不同的最优解改怎么办呢? 我们来推导一下
k=1
f[1] max( f[1]-1*w+1*w)
k=1
f[2] max(f[2]-2*w+2*w,f[1]-1*w+2*w)
k=1
f[3] max(f[3]-3*w+3*w,f[2]-2*w+3*w,f[1]-1*w+3*w)
于是我们发现
f[k]=f[k]-kw+kw f[n]=f[n]-nw+kw
所以我们可以对队列进行维护,所有存在队列里的值去掉 k*w 的部分

混合背包

题目链接: [http://codevs.cn/problem/3269/]
很裸的模板题了,我们直接开始写吧

二进制优化

时间: 4316 ms 内存: 1004 kb
#include <cstdio>
using namespace std;
int z,cnt,m;// 二进制拆分用
int n,V;// n 物品数量 V 体积
int v[10100000],w[10100000],alen;// v[] 体积 w[]价格 alen 长度
int f[10100000];// f[] 动归专用
int main(){
//读入
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v[alen],&w[alen],&m);
  z=alen;// 将 z 保留住
        alen++;
        if(m==-1) m=V/v[z]; //如果为无限的话,就按能放下的最大值走
        cnt=m-1;//-1是因为已经有 1 了
       //开始拆分
  for(int j=2;;j*=2){
            if(cnt>j){//如果还能拆,继续插并增加物品件数
                cnt-=j;
                v[alen]=v[z]*j;
                w[alen]=w[z]*j;
                alen++;
            }
            else {
                v[alen]=v[z]*cnt;
                w[alen]=w[z]*cnt;
                alen++;
                break;
            }
        }
    }
// dp[] 二进制拆分玩就是一个 01 背包了
    for(int i=0;i<alen;i++){
        for(int j=V;j>=v[i];j--){
            if(f[ j-v[i] ]+w[i]>f[j]){
                f[j]=f[ j-v[i] ]+w[i];
            }
        }
    }
    printf("%d",f[V]);
}

单调队列

时间: 2430 ms 内存: 2 MB
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];// dp[]
struct node {
    int f,id;
}q[210000];
int l,r;
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) m=V/v;
        for(int j=0;j<v;j++){
            l=r=0;
            for(int k=j,id=0;k<=V;k+=v,id++){
                while(l!=r&&q[r-1].f<=f[k]-id*w) r--;// 如果队尾解不如当前解就去掉
                q[r++]=node{f[k]-id*w,id};
                while(l!=r&&id-q[l].id>m) l++;// 如果目前所有的所有数量也达不到队首要求也去掉
                f[k]=q[l].f+id*w;
            }
        }
    }
    printf("%d",f[V]);
}

极限优化


时间: 1952 ms 内存: 2 Mb
#include <cstdio>
#include <iostream>
using namespace std;
int n,V,v,w,m;
int f[210000];
struct node {
    int f,id;
}q[210000];
int l,r;
// 01背包
void oz(int v,int w){
    for(int i=V;i>=v;i--){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 完全背包
void wq(int v,int w){
    for(int i=v;i<=V;i++){
       f[i]=max(f[i],f[i-v]+w);
    }
}
// 单调队列优化多重背包
void queueyh(int v,int w,int m){
    for(int j=0;j<v;j++){
        l=r=0;
        for(int k=j,id=0;k<=V;k+=v,id++){
            while(l!=r&&q[r-1].f<=f[k]-id*w) r--;
            q[r++]=node{f[k]-id*w,id};
            while(l!=r&&id-q[l].id>m) l++;
            f[k]=q[l].f+id*w;
        }
    }
}
int main(){
    scanf("%d%d",&n,&V);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&v,&w,&m);
        if(m==-1||m*v>V) wq(v,w);// 如果m都放进来已经大于背包就可以直接用无限
        else if(m==1) oz(v,w);// 只有1个就交给01背包吧
        else queueyh(v,w,m);
    }
    printf("%d",f[V]);
}

END

多重背包实际上与前两中差别不大,不过重点在于优化,优化不得当直接TLE ]]>

初学DP (1) – 01 背包 – 装箱问题 & NOIP 2005 普及 第三题 采药

DP

动态规划
我们知道,贪心的方法是取全局最优解,而 DP 是指通过解决局部最优解,来找到整个问题的最优解,我们来用看看下面这个求最短路的例子:
    / 2 \
1 - 3   - 5
   \ 4   /
我们求从 1 到 5 的的最短路,首先我们应该求出 1->2/3/4 的最短路,我们已经知道了 f(1) ( 1 的最短路)=1,将其移动到并算出 1->2 的最短路的过程就叫状态转移,而 f(1) 就是所谓的状态。 另外我们知道2/3/4 是同一层的东西,所以我们称这几个叫做”阶段”,1 也是一个阶段。 另外再来说说DP,需要满足的一些条件
  • 无后效性
  • 最优子结构
最优子结构是指”每个阶段的最优状态可以从之前某个阶段的某个或某些状态得到” 而无后效性是指”前面得到的解,对后面没有影响”

装箱问题

题目链接: [http://codevs.cn/problem/1014/] 首先我们第一个想到的是贪心,不过你尽管贪,能 A 算我输 我们先看代码吧qwq
#include <stdio.h>
int n,v;
int a[40],f[40][210000];
int main(){
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            if(f[i-1][j-a[i]]+a[i]>f[i-1][j]) f[i][j]=f[i-1][j-a[i]]+a[i];
            else f[i][j]=f[i-1][j];
        }
        for(int j=1;j<a[i];j++) f[i][j]=f[i-1][j];
    }
    printf("%d",v-f[n][v]);
}
a[] 价格 f[i][j] 当第 i 个物品被放进来时,容量为 j 的箱子最多可以放多少. 所以我们可以很容易得到下面这个状态转移方程
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
将这个方程输入进程序,你的第一道dp就完成了

循环 j ?


for(int j=v;j>=a[i];j–)
为什么 j 要倒着来?他能正这来吗? 当然是不能 如果你有心情手推你会发现,它正着来的时候会累加qwq 没错这就是完全背包,有关完全背包,我们过几次就会讲了

采药

题目链接: [https://www.luogu.org/problemnew/show/P1048] 不止这一家有这道题的说~
对比一下上面的装箱问题,我们可以发现,他们很相似,不过采药比装箱多以一个项目 – 时间 但是这显然不打扰,把 j 对应改成时间就行了 不过再让我们看看,这个二维数组,到底有没有必要
f[i][j]=max( f [ i-1] [ j – a [ i ] ] + a [ i ] , f [ i – 1 ] [ j ] )
我们只用到了 i-1 !!! 所以我们可以把方程化成下面这个
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
#include <cstdio>
using namespace std;
int t,m;
int time[110],pri[110],f[1100];
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&time[i],&pri[i]);
    for(int i=1;i<=m;i++){
        for(int j=t;j>=time[i];j--){
            if(f[j]<f[ j-time[i] ]+pri[i]){
                f[j]=f[ j-time[i] ]+pri[i];
            }
        }
    }
    printf("%d",f[t]);
}

01背包

说了这么多,让我们总结一下 01 背包 这种类型 针对于有一定空间,一定数量的物品,每个物品只能放一个,我们可以把他当为 01 背包,它的状态转移方程是:
f[j]=max( f [ j – a [ i ] ] + a [ i ] , f [ j ] )
]]>