仓库搬迁 题解

一些初入dp的选手，可能对于dp的学习感到十分不解，状态怎么设？转移怎么转？约束转移的条件怎么设？边界条件怎么判断？不可达状态又是什么？

看教练教，看网上题解，终归是感觉差了点自己的东西，我这篇题解会多一些我自己的思考，多一些细致的内容，目的是帮初学dp的选手进一步领悟dp的本质

题意

给定$n$个仓库，对于仓库$i$，有$c_i$的容量,并且仓库已经存在$a_i$的物品，保证$0\leq a_i\leq c_i$,可以选择搬迁一个仓库$j$,其中所有物品$a_j$会被搬迁出来，任意分配到没有选择搬迁（即保留）的仓库的空余位置 求最少保留仓库的数量，以及在此条件下最少搬迁物品的数量

分析

对于两个答案，我们可以分段求解

q1 最少的保留仓库数量 可转化为，保留至少多少的仓库，能使它们的容量和足以容纳所有的物品？ 很容易想到，把这些仓库的数据用结构体存储，基于$c_i$从大到小排序，贪心选取大的容量，直到容量和$\geq\sum_{i=1}^{n} a_i$ 此时q1得解，代码如下

struct node{
    int a,c;
}no[N];
bool cmp(node x,node y){
    return x.c>y.c;
}//从大到小排序容量
int main() {	
    int n,s=0;cin>>n;//记s为总的a和，dp用到
    for(int i=1;i<=n;i++)cin>>no[i].a>>no[i].c,s+=no[i].a;//读入，顺手累加s
    sort(no+1,no+n+1,cmp);//结构体排序
    int cnt=0,mi=0;//cnt为c的容量和，mi为最少的保留数
    for(int i=1;i<=n;i++){
        cnt+=no[i].c;
        if(cnt>=s&&mi==0)mi=i;
    }

q2 在最小保留仓库的情况下，最少的搬迁物品数量

因为总物品数量不变，最少的搬迁物品数量等价于最多的保留物品数量。 第一步没有较为明显的算法浮现在脑海，我们可以观察数据和题意 数据 ：保证$1\leq n\leq60$，$0\leq a_i\leq c_i \leq 3000$,并且$\sum_{i=1}^{n} a_i \leq 3000$ 非常特殊的数据，可以想到dp，再观察题意，对于仓库$i$，要么保留，要么搬迁，那么就是01背包dp，选取与否

dp的设计

dp有几大要素，状态，转移，边界，答案，细分的，还有转移中的约束条件，状态中的数组优化，时空优化等等

对于状态的设计，我们可以去枚举所有的状态，进一步辅助我们思考，简化转移的过程

状态

本题中 我们要以枚举的每一个（即i）仓库为基准，那么状态有如下几种，是可以自己思考+观察题意得出 1.已经选取保留的仓库 j
2.已经选取保留仓库的容量k 3.搬迁物品的数量o 4.保留物品的数量p 不难发现，在最后考虑n个仓库的情况下，搬迁物品的数量o是可以通过总物品数量s-保留物品数量p得到的，并且状态o的最小值，等价于状态p的最大值为我们要求解的答案 所以可以把这两个状态合并为一个作为答案，我们就得到了一个可以尝试的状态 记$f_{i,j,k}$为考虑前$i$个仓库，选取了$j$个仓库保留，保留仓库的容量至少为$k$时最大的保留物品数量

转移

01背包为什么称作01背包，是因为只有选取与否，相应的，转移也只有两种，要么是保留，要么是不保留（搬迁）

保留

我们思考，保留了仓库i，会使状态的总容量增加，选取保留量增加，选取保留物品数增加，所以可以用递推$f_{i,j,k+no[i].c}=max(f_{i,j,k+no[i].c},f_{i-1,j-1,k}+no[i].a)$ 因为容量总和大于等于物品总和s时才有答案，可以将容量熔断在s，即超过s的容量视为s int nk=min(s,k+no[i].c); 再将转移的$k+no[i].c$替换为nk即可 约束条件要从转移中思考，因为j可能取到0，即不保留仓库，那么j-1==-1时显然不合法，我们约束在j>=1,并且$f_{i-1,j-1,k}$可能不合达，那么要在前面的边界中预处理不合法状态，再在这一步约束在这个状态合法的条件才能转移

不保留

不保留这个仓库时，保留仓库的物品和并没有改变，j也没有改变，所以转移公式简单明了 $f_{i,j,k}=max(f_{i,j,k},f_{i-1,j,k})$ 约束条件也很简单，只需要判断$f_{i-1,j,k}$是否可达就行

答案

因为我们已经熔断了大于s的其他容量，所以只需要考虑容量为s的情况，其中我们在前面求过最少保留的仓库数量为mi，那么答案就为 $f_{n,mi,s}$

边界

我们只需初始化$f_{*,*,*}$ 都记为$-inf$不可达状态 再使得$f_{0,0,0}=0$,就简化了定义边界的过程

code

#include <bits/stdc++.h>
using namespace std;
const int N=69,M=3e3+9,inf=1e9+9;
int f[N][N][M];//记fi j k为考虑前i个仓库,保留了j个，且当前容量至少为k时的最大保留和 
struct node{
    int a,c;
}no[N];
bool cmp(node x,node y){
    return x.c>y.c;
}//以容量排序 
int main() {	
    int n,s=0;cin>>n;
    for(int i=1;i<=n;i++)cin>>no[i].a>>no[i].c,s+=no[i].a;//读入，顺手维护s为总a和 
    sort(no+1,no+n+1,cmp);
    int cnt=0,mi=0;//容量和，最少保留数 
    for(int i=1;i<=n;i++){
        cnt+=no[i].c;
        if(cnt>=s&&mi==0)mi=i;
    }
    //前置重要：node统计a,c，最小保留数 
    //边界 
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=s;k++)f[i][j][k]=-inf;
    f[0][0][0]=0; 
    
    for(int i=1;i<=n;i++){//转移这一步，思考什么条件才可以转移 
        for(int j=0;j<=i;j++){//不保留或保留 
            for(int k=0;k<=s;k++){
                if(j-1>=0&&f[i-1][j-1][k]>=0){//约束条件 
                    int nk=min(s,k+no[i].c);//熔断 
                    f[i][j][nk]=max(f[i][j][nk],f[i-1][j-1][k]+no[i].a);
                } 
                if(f[i-1][j][k]>=0)f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
            }
        }
    } 
    cout<<mi<<' '<<s-f[n][mi][s];//答案 
	return 0; 
}