博客

背包简单问题

  • Post author:
  • Post category:其他


目录



学习篇+?板子?



01背包问题 求优解


N种物品，总容量V，每种物品只能选一次，求不超过V的最优解（以下为求最大价值）


本质：选和不选的问题



朴素做法O（NV）

初始化问题：（以下指的是一维的情况）

1、可以不装满：

求最优解：memset(dp,0,sizeof dp);

2、必须装满

求最大值：

dp[0]=0;

for(int i=1;i<=V;i++) dp[i]=-0x3f3f3f3f;

最后 dp[V]!=-0x3f3f3f3f 则输出解，否则无解

求最小值：

dp[0]=0;

for(int i=1;i<=V;i++) dp[i]=0x3f3f3f3f;

最后 dp[V]!=0x3f3f3f3f 则输出解，否则无解


二维：
 

       for(int i=1;i<=n;i++){
            for(int j=0;j<=V;j++){
                dp[i][j]=dp[i-1][j];//不选
                if(j>=v[i])dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i] );//选
            }
        }


空间优化一维：
 

       for(int i=1;i<=n;i++){
            for(int j=V;j>=v[i];j--){
                dp[j]=max(dp[j] , dp[j-v[i]]+w[i] );
            }
        }



常数优化

这是别人讲的（我不太理解这种说法）

在这里插入图片描述

总之 j 的范围就是：

在这里插入图片描述

理解：

如果取完剩下的 i到n个物品，剩下的空间还是比v[i]大（就是还有空间留给下一个将要装入背包的物体），

那就不用更新更左边的体积的最大价值（因为接下来的更新用不到那么左边的价值），

不过只对背包求最大价值这题成立，其他情况下可能不成立（eg：求多少种价值）。 

        for(int i=1;i<=n;i++){
            int mi=max(V-sum,v[i]);

            for(int j=V;j>=mi;j--){
                dp[j]=max(dp[j] , dp[j-v[i]]+w[i] );
            }

            sum-=v[i];
        }



完全背包 求最优解


N种物品，总容量V，每种物品有无限多个，求不超过V的最优解（以下为求最大价值）


本质：第i种物品，第k个物品选与不选



O（NM）做法

        for(int i=1;i<=n;i++)
            for(int j=v[i];j<=V;j++)
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);



多重背包 求最优解


N种物品，总容量V，每种物品只有s[i]个，求不超过V的最优解（以下为求最大价值）


本质：很完全背包差不多只是每种物品有限制次数



朴素做法 O(NVS)

        for(int i=1;i<=n;i++){
            int m=min(s[i],V/v[i]);
            for(int k=1;k<=m;k++){
                for(int j=V;j>=v[i];j--){
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }



二进制优化 O(NVlog(S))

将每种物品的个数，分解成：2^0 ,2^1, 2^2, ····，剩余，在这些分解的个数做01背包

正常做法：

但是这样的做法就要算出cnt的最大范围：N*(log(S)+1) , log（S）表示以二为底的S的对数，利用计算机求 

        int cnt=0;
        for(int i=1;i<=n;i++){
            int vv,ww,ss;cin>>vv>>ww>>ss;
            for(int k=1;k<=ss;k*=2){
                v[++cnt]=vv*k;
                w[cnt]=ww*k;
                ss-=k;
            }
            if(ss){
                v[++cnt]=ss*vv;
                w[cnt]=ss*ww;
            }
        }
        //01背包
        for(int i=1;i<=cnt;i++){
            for(int j=V;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }

合并做法：

优点：不需要求cnt最大范围 

        for(int i=1;i<=n;i++){
            int ss=min(V/v[i],s[i]);//可能取不到s[i]
            for(int k=1;ss>0;k<<=1){
                if(k>ss)k=ss;//将剩余值赋给k
                ss-=k;
                for(int j=V;j>=v[i]*k;j--){
                    dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
                }
            }
            
        }



单调队列优化 O(NV)

这个我怎么都没学明白他的分析，以后再说


有篇模板



有篇分析

不懂不懂不懂我看了好多篇我还是不懂烦死花了好多时间还不懂



水题集



hdu 2602：01背包求最大值


hdu 2602

做法一：一维 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//01背包
//1、dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i] )
//2、dp[j]=max(dp[j],dp[j-v[i]]+w[i])
//3、常数优化
int v[1010],w[1010],dp[1010];//v存体积，w存价值
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,V;cin>>n>>V;
        for(int i=1;i<=n;i++)cin>>w[i];
        for(int i=1;i<=n;i++)cin>>v[i];
        memset(dp,0,sizeof dp);

        for(int i=1;i<=n;i++){
            for(int j=V;j>=v[i];j--){
                dp[j]=max(dp[j] , dp[j-v[i]]+w[i] );
            }
        }
        cout<<dp[V]<<endl;
    }
    return 0;
}

做法二：一维常数优化 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//01背包
//1、dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i] )
//2、dp[j]=max(dp[j],dp[j-v[i]]+w[i])
//3、常数优化
int v[1010],w[1010],dp[1010];//v存体积，w存价值
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,V,sum=0;cin>>n>>V;
        for(int i=1;i<=n;i++)cin>>w[i];
        for(int i=1;i<=n;i++){cin>>v[i];sum+=v[i];}
        memset(dp,0,sizeof dp);

        for(int i=1;i<=n;i++){
            int mi=max(V-sum,v[i]);

            for(int j=V;j>=mi;j--){
                dp[j]=max(dp[j] , dp[j-v[i]]+w[i] );
            }

            sum-=v[i];
        }
        cout<<dp[V]<<endl;
    }
    return 0;
}

做法三：二维 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//01背包
//1、dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i] )
//2、dp[j]=max(dp[j],dp[j-v[i]]+w[i])
//3、常数优化
int v[1010],w[1010],dp[1010][1010];//v存体积，w存价值
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n,V;cin>>n>>V;
        for(int i=1;i<=n;i++)cin>>w[i];
        for(int i=1;i<=n;i++)cin>>v[i];
        memset(dp,0,sizeof dp);

        for(int i=1;i<=n;i++){
            for(int j=0;j<=V;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=v[i])dp[i][j]=max(dp[i-1][j] , dp[i-1][j-v[i]]+w[i] );
            }
        }
        cout<<dp[n][V]<<endl;
    }
    return 0;
}



hdu 1114：完全背包+装满


hdu 1114
 

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

//完全背包+装满的情况
//dp[j]=min(dp[j],dp[j-v[i]]+w[i]);顺序
//初始化：0x3f3f3f3f

int v[510],w[510],dp[10010];//v存重量，w存价值
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int v0,v1,V;cin>>v0>>v1; V=v1-v0;
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>w[i]>>v[i];

        dp[0]=0;
        for(int i=1;i<=V;i++)dp[i]=inf;

        for(int i=1;i<=n;i++){
            for(int j=v[i];j<=V;j++){
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        if(dp[V]==inf)cout<<"This is impossible."<<endl;
        else cout<<"The minimum amount of money in the piggy-bank is "<<dp[V]<<"."<<endl;
    }
    return 0;
}



hdu 2191：多重背包


hdu 2191

做法一：二进制优化未合并 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500;//N=100*（log2(20)+1）=100*5//以二为底的20的对数 可以利用计算机求
//const int M=110;
//多重背包
//1、二进制优化
//2、单调队列优化

int v[N],w[N],dp[110];//v存每袋价钱，w存每袋重量，s存每种米数量
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int V,n;cin>>V>>n;
        memset(dp,0,sizeof dp);
        
        int cnt=0;
        for(int i=1;i<=n;i++){
            int vv,ww,ss;cin>>vv>>ww>>ss;
            for(int k=1;k<=ss;k*=2){
                v[++cnt]=vv*k;
                w[cnt]=ww*k;
                ss-=k;
            }
            if(ss){
                v[++cnt]=ss*vv;
                w[cnt]=ss*ww;
            }
        }

        for(int i=1;i<=cnt;i++){
            for(int j=V;j>=v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }

        cout<<dp[V]<<endl;

    }
    return 0;
}

做法二：二进制优化合并 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500;//N=100*（log2(20)+1）=100*5//以二为底的20的对数 可以利用计算机求
//const int M=110;
//多重背包
//1、二进制优化
//2、单调队列优化

int v[110],w[110],s[110],dp[110];//v存每袋价钱，w存每袋重量，s存每种米数量
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int V,n;cin>>V>>n;
        for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
        memset(dp,0,sizeof dp);
        
        for(int i=1;i<=n;i++){
            int mi=min(V/v[i],s[i]);
            for(int k=1;mi>0;k<<=1){
                if(k>mi)k=mi;
                mi-=k;
                for(int j=V;j>=v[i]*k;j--){
                    dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
                }
            }
            
        }
        
        cout<<dp[V]<<endl;

    }
    return 0;
}

做法三：朴素做法

这题能过 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
//const int N=500;//N=100*（log2(20)+1）=100*5//以二为底的20的对数 可以利用计算机求
//const int M=110;
//多重背包
//1、二进制优化
//2、单调队列优化

int v[110],w[110],s[110],dp[110];//v存每袋价钱，w存每袋重量，s存每种米数量
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int V,n;cin>>V>>n;
        for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
        memset(dp,0,sizeof dp);

        for(int i=1;i<=n;i++){
            int m=min(s[i],V/v[i]);
            for(int k=1;k<=m;k++){
                for(int j=V;j>=v[i];j--){
                    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
                }
            }
        }

        cout<<dp[V]<<endl;

    }
    return 0;
}



hdu 1284：类完全背包


hdu 1284
 

#include <bits/stdc++.h>
#define ll long long
using namespace std;


//完全背包
// V=N ,题中三种物品的价钱即是体积也是价值， 求dp[V]时花费的最大价钱 ，则题解：V-dp[V];

int a[5],dp[10010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int V;cin>>V;
        a[1]=150;a[2]=200;a[3]=350;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=3;i++){
            for(int j=a[i];j<=V;j++){
                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
            }
        }
        cout<<V-dp[V]<<endl;
    }
    return 0;
}



hdu 4508：类完全背包


hdu 4508
 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//完全背包
// v[i]=卡路里 w[i]=幸福程度 V=m
//dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

int v[110],w[110],dp[100010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
        int V;cin>>V;

        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=v[i];j<=V;j++){
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        cout<<dp[V]<<endl;

    }
    return 0;
}


版权声明：本文为weixin_52723996原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。