背包九讲

01背包

01背包九讲里面最简单的一种了,但是也是最重要的一种,其他的几种基本上都可以用01背包的解题思路来去解决,接下来结合例题来解决一下吧;

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数,表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例: 8

这个题可以说是最直白的01背包了,我们可以用一个二维的滚动数组来存背包当前是否能装的下这件物品,然后从第一个到以后一个物品一个一个的便利,然后用数组的列表示当前背包容量为j的时候可以装的最大价值是多少;如果j小于当前的重量,那么就能装的下,他的容积就是上一个物品时的价值;说的不是很清楚直接看代码吧!

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN];    // 重量 
int v[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j重量下前i个物品的最大价值 
int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> w[i] >> v[i];
    for(int i = 1; i <= n; ++i) //依次便利每个背包
        for(int j = 1; j<=m; ++j)
        {
            //  当前重量装不进,价值等于前i-1个物品
            if(j<w[i]) 
                f[i][j] = f[i-1][j];
            // 能装,需判断 是放这个物品的价值打还是不放这个物品价值大
            else    
                f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+v[i]);
        }           

    return 0;
}

其是还可以对空间复杂度进行一波优化

#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],dp[N]={0};
int main()
{
    int n,V;
    cin >> n >> V;
    for(int i=1;i<=n;i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=V;j;j--)
        {
            if(j>=v[i])dp[j]=max(dp[j-v[i]]+w[i],dp[j]);//这里改用了一维的;
        }
    cout << dp[V];
    return 0;
}

完全背包

完全背包和01背包的不同之处就是完全背包的每个物品可以被无限次的拿,而01的只能被拿一次; 这里我们只说一个优化空间复杂度过的版本,直接看例题吧

有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。 第 i 种物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。 输出格式 输出一个整数,表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例: 10

01背包是是从大倒下一次遍历背包的容量,这是为了避免重复的那一个值,我我们可以从小到大一次遍历,加入背包的容量为5,第一个物品的价值为2体积为1;当j等一的时候我们遍历了一次,然后dp[1]=2;当j=2时dp[2]=max(dp[2],dp[2-1]+2);这样刚好有取了一遍是不是很巧?我们只要从开始一直遍历到最后就可以了;然后输出dp[V]就可以了;

#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1010;
int n,m;
int dp[N];
int v[N];
int w[N];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> v[i] >> w[i];
    }
    for(int i = 1;i<=n;i++){
        for(int j = v[i];j <= m ;j++){
            arr[j] = max(dp[j] , dp[j-v[i]]+w[i]);//每次保留最大的
        }
    }
    cout <<dp[m];
    return 0;   
}

多重背包

1

有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 输出格式 输出一个整数,表示最大价值。 数据范围 0<N,V≤100 0<vi,wi,si≤100 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例: 10

这个是最最基础的多重背包了,我们只需要加上一个循环作为判断就行了

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int w[MAXN];    // 重量 
int v[MAXN];    // 价值 
int s[MAXN];    // 物品数量 
int f[MAXN];    // f[i][j], j重量下前i个物品的最大价值 
int main() 
{
    int n;
    int m;  // 背包重量 
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        cin >> w[i] >> v[i] >> s[i];
    for(int i = 1; i <= n; ++i)
        for(int j = m; j>=0; --j)   
            for(int k = 1; k <= s[i]; ++k) //遍历拿几个的时候最大
                if(j>=k*w[i])
                    f[j] = max(f[j], f[j-k*w[i]]+k*v[i]);
    cout << f[m] << endl;

    return 0;
}

2

1的时间复杂度是nmk的如果遇到数据比较就没办法了需要进行优化我们这次说的是二进制优化;

有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 输出格式 输出一个整数,表示最大价值。 数据范围 0<N≤1000 0<V≤2000 0<vi,wi,si≤2000 提示: 本题考查多重背包的二进制优化方法。 输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2 输出样例: 10

这一题如果我们直接暴力搜索那么肯定会超时的,所以需要进行一些优化,emmm什么一次呢,第一种情况是从0到k每次去不同的数,那么我们能不能想办法将这个过程给优化一波呢?答案是可以的,例如7以内的数我们可以用1,2,4这三个数表示。3=1+2,5=1+4;6=2+4;7=1+2+4,因此我们可以用二进制的性质将k进行优化

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int n,m,v,w,s;
int dp[3000];
vector<int>ve;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>v>>w>>s;
        ve.clear() ;
        for(int q=1;q<s;q<<=1)//将 s 用 二进制的数表示 每次将 q 乘以2,保证是2的整数次方 
        {
            s-=q;
            ve.push_back(q); 
        }
        if(s) ve.push_back(s);  //如果最后s有剩余,就单独放入; 
        for(int k=0;k<ve.size();k++)
        {
            for(int j=m;j>=v*ve[k];j--)//遍历ve中的数据作为01背包,每个数据只会有取和不去的两种选项 
            {
                dp[j]=max(dp[j],dp[j-ve[k]*v]+ve[k]*w);
            }
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

3

emmm第三种还不是很会,用到的知识是单调队列!有兴趣的可以自己学习一下

混合背包

混合背包就是讲前面的几种情况混合起来了,我们计算的时候只用分类计算就行了,还是之前的问题

有 N 种物品和一个容量是 V 的背包。 物品一共有三类: 第一类物品只能用1次(01背包); 第二类物品可以用无限次(完全背包); 第三类物品最多只能用 si 次(多重背包); 每种体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。 接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。 si=−1 表示第 i 种物品只能用1次; si=0 表示第 i 种物品可以用无限次; si>0 表示第 i 种物品可以使用 si 次; 输出格式 输出一个整数,表示最大价值。 数据范围 0<N,V≤1000 0<vi,wi≤1000 −1≤si≤1000 输入样例 4 5 1 2 -1 2 4 1 3 4 0 4 5 2 输出样例: 8

这一题直接分类计算就行了

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;

int n,m,v,w,s;
int dp[3000];
vector<int>ve;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>w>>v>>s;
        ve.clear() ;
        if(s>0){  //如果是多重的用二进制进行优化
            for(int p=1;p<s;p<<=1)
            {
                ve.push_back(p);
                s=s-p; 
            }
            if(s) ve.push_back(s); 
        }
        if(!s)//完全背包
        {
            for(int j=w;j<=m;j++)
            {
                dp[j]=max(dp[j],dp[j-w]+v);
            }
        }
        else if(s>0){//多重背包
            for(int k=0;k<ve.size();k++)
            {
                for(int j=m;j>=w*ve[k];j--)
                dp[j]=max(dp[j],dp[j-w*ve[k]]+ve[k]*v);
            }
        }
        else{//01背包
            for(int j=m;j>=w;j--)
            {
                dp[j]=max(dp[j],dp[j-w]+v);
            }
        }    
    }
    cout<<dp[m]<<endl;
    return 0;
}

二维费用的背包问题

其实二维费用背包也是很简单的就是将滚动数组多开一维用来分别存储体积和质量罢了!

有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。 每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。 求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。 输出最大价值。 输入格式 第一行两个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。 接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。 输出格式 输出一个整数,表示最大价值。 数据范围 0<N≤1000 0<V,M≤100 0<vi,mi≤100 0<wi≤1000 输入样例 4 5 6 1 2 3 2 4 4 3 4 5 4 5 6 输出样例: 8

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int n,V,M;
int dp[1500][1500];
int v,m,w;

int main()
{
    cin>>n>>V>>M;
    for(int i=0;i<n;i++)
    {
        cin>>v>>w>>m;
        for(int j=V;j>=v;j--)//两个循环分别遍历体积的质量遍历的规则和一维的一样
        {
            for(int k=M;k>=w;k--)
            {
                dp[j][k]=max(dp[j][k],dp[j-v][k-w]+m);
            }
        }
    }
    cout<<dp[V][M]<<endl;
    return 0;
}

背包问题求方案数

这类问题我们只需要再开一个数组标记方案书就行了中间有点小细节注意一下

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7 的结果。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数,表示 方案数 模 109+7 的结果。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 6 输出样例: 2

#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

int dp[1090];
int flag[1090];
int n,v,V,m;
const int mod=1e9+7;
int main()
{
    cin>>n>>V;
    flag[0]=1;
    for(int i=0;i<n;i++)
    {
        cin>>v>>m;

        for(int j=V;j>=v;j--)
        {   
            int s=0;
            int t=max(dp[j],dp[j-v]+m);//还和之前的一样遍历只是中间需要记录路径数所以不能直接赋值
            if(t==dp[j]) s+=flag[j];//当t=dp[j]时s加上flag【j】
            if(t==dp[j-v]+m) s=s+flag[j-v];//当t=dp[j-v]+m时s加上flag[j-v]
            flag[j]=s%mod;//注意取mod 只是因为  有可能两种不同的路径取出来的最大值是相同的
            dp[j]=t;
        }
    }
    int maxn=-1;
    int sum=0;
    for(int i=0;i<=V;i++) maxn=max(maxn,dp[i]);//遍历最大值
    for(int i=0;i<=V;i++)
    {
        if(dp[i]==maxn)
        {
            sum=(sum+flag[i])%mod;//路径相加
        }
    }
    cout<<sum<<endl;
    return 0;
}

背包问题求具体方案

这个问题看上去和上一个很像但是区别还是不小的吧

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出 字典序最小的方案。这里的字典序是指:所选物品的编号所构成的序列。物品的编号范围是 1…N。 输入格式 第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。 接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。 输出格式 输出一行,包含若干个用空格隔开的整数,表示最优解中所选物品的编号序列,且该编号序列的字典序最小。 物品编号范围是 1…N。 数据范围 0<N,V≤1000 0<vi,wi≤1000 输入样例 4 5 1 2 2 4 3 4 4 6 输出样例: 1 4

用一个标记数组进行标记然后从大到小遍历,每次标记被取得,然后再从小到大进行查找

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int n,v[1500],w[1500],m;
int f[1500],dp[1500][1500];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--)//因为需要标记所以用二维的数组进行储存
    {
        for(int j=0;j<=m;j++)
        {
          if(j<v[i]) dp[i][j]=dp[i+1][j];
          else 
          dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]]+w[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(m-v[i]>=0&&dp[i][m]==dp[i+1][m-v[i]]+w[i])//如果满足条件就进行输出
        {
            cout<<i<<" ";
            m-=v[i];//进行查找下一个位置,这个节点连接的,可能有点难理解自己画个图模拟一遍就可以了
        }
        if(m==0) break;
    }
    return 0;
}

有依赖的背包问题

这个是真不会还用到了树形dp,分组背包,emmm以后再补吧

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树的直径

    这个题刚开始一直不理解,可能是对树的的直径比较陌生吧,可后来看看了看学长给我板子。我去咋这么简单emmm,我真是个智障呀。只要从任意一个节点出发然后找到距离他最...

    某些人
  • HDU-1811-Rank of Tetris

    #HDU-1811-Rank of Tetris HDU-1811-Rank of Tetris

    某些人
  • D. Minimax Problem

    time limit per test:5 seconds memory limit per test:512 megabytes inputstandard ...

    某些人
  • 额,没想到,背包问题解题也有套路。。。

    背包问题是一类比较 特殊的动态规划 问题,这篇文章的侧重点会在答案的推导过程上,我们还是会使用之前提到的解动态规划问题的四个步骤来思考这类问题。

    五分钟学算法
  • 初识背包问题之 「 0-1 背包 」

    背包问题可以说是一个老生常谈的问题,通常被用作面试题来考查面试者对动归的理解,我们经常说学算法,初学者最难理解的就是 “二归”,一个叫递归,另一个叫动归。

    五分钟学算法
  • 动态规划之01背包详解【解题报告】

    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01...

    Angel_Kitty
  • Hiho Coder 1038 01背包(模板)

           01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci,得到的价值是Wi,求将哪些物品装入背包可使获得的价值总和最大。而...

    Ch_Zaqdt
  • HDU-6006-Engineer Assignment

    ACM模版 描述 ? 题解 常规的状压 DPDP 套路。 给定 NN 个任务和 MM 个工程师,每个任务都有不超过三个的领域人才需求,每个工程师都有不超过两个领...

    f_zyj
  • 树状数组 单点修改 区间查询

    用户2965768
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433

扫码关注云+社区

领取腾讯云代金券