DP训练——背包DP

作者: 云中翻月 | 来源:发表于2020-02-23 15:07 被阅读0次

背包DP

POJ3093
题意
给定 $V(V<=30)$ 个物品和背包容量 $D(D<=1000)$ ，求将背包尽量放满的方案数。（尽量放满指的是剩余物品中重量最小的物品都不能再放入背包）
题解
考虑到背包要放的尽量满，所以额外枚举一下没有放入背包的最小物品即可。
具体实现上，可以先将重量升序排序，然后枚举第k个物品最终没有放入背包。
则第 $1$ 到第 $k-1$ 的物品必然放入背包，同时对第 $k+1$ 到第 $V$ 的物品做01背包后，将满足条件的方案数统计下即可。
状态定义： $d[j]$ 表示去掉不放入背包的最小物品 $k$ 后，背包装入总重量为 $j$ 的方案数
目标： $\sum_{j=max(maxD-v[k]+1,0)}^{maxD}d[j]$ ( $maxD$ 为前 $k-1$ 个物品已放入背包后，背包的最大容量)
边界： $d[0]=1$
转移方程： $d[j]=d[j]+d[j-v[i]],k+1\leq i\leq n$
PS：本题存在如下坑点。
1 一个物品都放不进背包的情况被视为方案数为 $0$ ，因此需要在开始位置特判。
2 所有物品全放入背包都可以的情况被视为方案数为 $1$ ，同样需要特判。
3 当枚举到第 $k$ 个物品放入背包后，背包恰好放满的情况下，当前的答案就是 $1$ ，不再进行dp。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxv=30+5;
const int maxd=1000+5;
const int INF=0x3f3f3f3f;
int T,kase=0;
int V,D;
int v[maxv];
int sum[maxv];
ll d[maxd];
ll ans;
void init(){
    ans=0ll;
}
void dp(){
    for(int k=1;k<=V;k++){ //枚举剩余的最小物品k
        int maxD=D-sum[k-1]; //则前k-1个物品已经放入背包，背包的最大容量变为D-sum[k-1]
        if(maxD<0) break;
        if(maxD==0){
            ans++;
            continue;
        }
        memset(d,0,sizeof(d));
        d[0]=1;
        for(int i=k+1;i<=V;i++) for(int j=maxD;j>=v[i];j--) d[j]+=d[j-v[i]];
        for(int i=max(0,maxD-v[k]+1);i<=maxD;i++) ans+=d[i];
        /*
        for(int i=max(0,maxD-v[k]+1);i<=maxD;i++){
            D(k);D(maxD);D(i);D(d[i]);E;
        }
        */
    }
    if(sum[V]<=D) ans++;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("POJ3093.in","r",stdin);
    cin>>T;
    while(T--){
        cout<<++kase<<" ";
        cin>>V>>D;
        init();
        for(int i=1;i<=V;i++) cin>>v[i];
        sort(v+1,v+V+1);
        if(v[1]>D){
            cout<<0<<endl;
            continue;
        }
//        reverse(v+1,v+V+1);
        for(int i=1;i<=V;i++) sum[i]=sum[i-1]+v[i];
        dp();
        cout<<ans<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ2748
题意
给你初始数的大小 $beginlevel$ 和所能达到最大数的大小 $maxlevel(maxlevel<=1000)$ 。
再给你 $n(n<=50)$ 个数让你每次加上这个数或减去这个数，但不能超出区间 $[0,maxlevel]$ ，求最后得到的最大结果。
题解
因为每一层都有两个转移方向，同时又存在一层内没有任何一个合法的状态转移的情况。
因此，01背包时不能压缩掉第一个维度。（因为需要确定第 $n$ 层是否能转移到）
其他部分就是01背包的模板。
状态定义： $d[i,j]$ 表示处理完第i个物品，背包装入总重量为j的存在性
目标： $max(j),d[n,j]=1$
边界： $d[0][beginlevel]=1$
转移方程： $d[i,j]=\left\{\begin{matrix}d[i,j]|d[i-1,j-v[i]],0\leq j-v[i] & & \\ d[i,j]|d[i-1,j+v[i]],j+v[i]\leq maxlevel & & \end{matrix}\right.$
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50+5;
const int maxl=1000+5;
const int INF=0x3f3f3f3f;
int n,bl,ml,c[maxn];
int d[maxn][maxl];
void dp(){
    memset(d,0,sizeof(d));
    d[0][bl]=1;
    for(int i=1;i<=n;i++) for(int j=0;j<=ml;j++){
        if(j+c[i]<=ml) d[i][j]|=d[i-1][j+c[i]];
        if(j-c[i]>=0) d[i][j]|=d[i-1][j-c[i]];
    }
    for(int j=ml;j>=0;j--) if(d[n][j]){
        cout<<j;
        return;
    }
    cout<<-1;
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("2748.in","r",stdin);
    cin>>n>>bl>>ml;
    for(int i=1;i<=n;i++) cin>>c[i];
    dp();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ1190
题意
$n(n<=100)$ 个物品，选取若干个，使得重量不超过 $W(W<=2^{32})$ 的情况下，总价值最大。
数据保证每个物品的重量符合 $a*2^b(a<=10,b<=30)$
题解
这是一道按位划分后，从低位向高位做分层背包的题目。
首先，考虑利用题目数据的条件，即每个物品的质量都可以表示为 $a*2^b$ 的形式。
这意味着，如果按照 $b$ 的值，对所有物品进行分组后( $b=i$ 的物品属于第 $i$ 组)，每组内所有 $a$ 的值的和最大为 $1000(a<=10,n<=100)$ 。
我们将组号设为dp数组的第一维(范围 $[0,30]$ )，组内所有 $a$ 的值设为dp数组的第二维(范围 $[0,1000]$ )。
于是，dp数组的空间便可以承受。
状态定义： $d[i,k]$ 表示在只使用第i组内的物品，背包已经占用的重量为k的最大价值
目标：所有 $d$ 值，用于下一步计算
边界： $d[0,0]=0$
转移方程： $d[i,k]=max(d[i,k-G[i][j]]+V[i,j])$ ( $j$ 循环枚举第 $i$ 组内的所有物品，向量 $G$ 保存第 $i$ 组内的物品的 $a$ 值)
接下来考虑如何用上述dp数组，将所有组合并起来计算答案。
状态定义： $d[i,j]$ 表示在前i组中，背包已经占用的重量为 $j*2^i$ 加上 $W$ 二进制第 $i$ 位以下的体积的最大价值（可近似理解为对上述状态求前缀和）
目标： $d[len,1]$ (len表示 $2^{len}<=W$ 的最大的len，这就意味着需要考虑所有在转移方程中考虑 $W$ 几位上本来就有的 $1$ ，即对应转移方程中的 $(W>>i-1)\&1$ 和递推 $w$ 前缀和数组时的向上取整)
边界： $d[0,0]=0$
转移方程： $d[i,j]=max(d[i,j-k]+d[i-1,min(w[i-1],k*2+((W>>i-1)\& 1))])$ ( $k$ 循环枚举在 $i-1$ 组内选择的物品体积，则 $j-k$ 为在第 $i$ 组内选择的物品体积)
其他细节详见代码注释。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100+5;
const int maxa=10+5;
const int maxb=30+5;
const int maxm=1000+5;
const int INF=0x3f3f3f3f;
int n,W;
vector<int>G[maxb],V[maxb];
int w[maxb];
int d[maxb][maxm];
int len;
void init(){
    len=0;
    memset(d,0,sizeof(d));
    memset(w,0,sizeof(w));
    memset(G,0,sizeof(G));
    memset(V,0,sizeof(V));
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ1190.in","r",stdin);
    while(scanf("%d%d",&n,&W)){
        if(n==-1&&W==-1) break;
        init();
        int weight,value;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&weight,&value);
            int a,b=0;
            while(!(weight&1)) weight>>=1,b++;
            a=weight;
            len=max(len,b);
            G[b].push_back(a);
            w[b]+=a;
            V[b].push_back(value);
            //按照b的值分组，在每一组内记录对应的a作为重量，value作为价值
        }  
        //首先对每一组进行01背包
        //d[i,k]表示在第i组内，背包已经占用的重量为k的最大价值
        //这时len是组数
        for(int i=0;i<=len;i++){
            for(int j=0;j<G[i].size();j++){
                for(int k=w[i];k>=G[i][j];k--){
                    d[i][k]=max(d[i][k],d[i][k-G[i][j]]+V[i][j]);
                }
            }
        }
        while(W>>len) len++;
        len--;
        //这时len是表示2^len<=W的最大的len
//        D(len);E;
        //d[i,j]表示在第0~i组中，背包已经占用的重量为$j*2^_i$加上W二进制第i位以下的体积的最大价值
        for(int i=1;i<=len;i++){
            w[i]+=(w[i-1]+1)/2; //w[i]=w[i]+ceil(w[i-1]/2)
            for(int j=w[i];j>=0;j--){ //w[i]表示前i组背包的最大加权重量
                for(int k=0;k<=j;k++){
                    d[i][j]=max(d[i][j],d[i][j-k]+d[i-1][min(w[i-1],k*2+((W>>i-1)&1))]); //k*2是因为进了一位
                }
            }
        }
        //按照d的状态定义，答案就是d[len,1]
        printf("%d\n",d[len][1]);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

DP训练——背包DP

背包DP

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划