Logstash 深度图像 datatable datagridview ros 打印 vue案例 jq第一个子元素 jq去空格 jquery通过class获取元素 nginx默认端口号 时间戳java a标签去除下划线 pip环境变量 oracle连接字符串 mysql组合索引 hbuilder插件 python数据库 mysql 连接 python中的zip python中open python定义变量 java系统学习 怎么装linux系统 php网络编程 python下载教程 灼热峡谷 keytool下载 网络克隆 3389扫描器 一羽月土米水日古余打一成语 远程桌面管理软件 电脑cmd命令大全 黑客入门新手特训 txplatform cinema4d下载 dnf选择角色卡死 文件批量更名 dll文件 xlwt 清华天河
当前位置: 首页 > 学习教程  > 编程语言

算法日记——动态规划之背包问题

2020/9/19 14:32:32 文章标签:

算法日记——动态规划之背包问题

  • 前言
  • 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

解题思路
其他博客上的那些状态转移过于复杂,对于初学者来说不是很好理解,其实我们可以以集合的角度看这个问题。我们设f【i】【j】为集合 ,这个集合的含义呢就是在前i个物品里选,总体积不超过j的最大价值。这样呢我们就可以对第i个物品进行选择,1.选 2.不选。
状态转移方程:
定义f[i][j]:前i个物品,背包容量j下的最优解

1)当前背包容量不够(j < w[i]),为前i-1个物品最优解:f[i][j] = f[i-1][j]
2)当前背包容量够,判断选与不选第i个物品
选:f[i][j] = f[i-1][j-w[i]] + v[i]
不选:f[i][j] = f[i-1][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]);
        }           

    cout << f[n][m];
    return 0;
}


二维转一维

通常我们对动态规划维度优化是我们是对其代码进行等价代换。

  1. f[i] 仅用到了f[i-1]层,
  2. j与j-v[i] 均小于j;
  3. 3.若用到上一层的状态时,从大到小枚举, 反之从小到大。
    代码如下
#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[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 = m; j >= v[i]; j--) 
          f[j] = max(f[j], f[j-v[i]]+w[i]);
  cout << f[m] << endl;
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
解题思路
解题思路延续我们从集合角度看的思想,是不是可看成每个物品拿一个,拿两个,拿3个…
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-2v]+2*w , …)
由上两式,可得出如下递推关系:
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
朴素写法

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
   int n,m;
   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 = 0 ; j<=m ;j++)
   {
       for(int k = 0 ; k*v[i]<=j ; k++)
           f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
   }

   cout<<f[n][m]<<endl;
}

有了上面的关系,那么其实k循环可以不要了,核心代码优化成这样:

for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
    f[i][j] = f[i-1][j];
    if((j-v[i]>=0)
        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}

最终代码

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    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++)
    {
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}

多重背包

多重背包则是在原有问题上 多个数量限制,则每组可取的物品数是已知的。


有 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

解题思路

在01背包的基础上变成了有限制的01背包问题;

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N=101;
int s[N],v[N],w[N];
int f[N][N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
          for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
            f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<<f[n][m]<<endl;
    return 0;
}

分组背包


有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;
输出格式
输出一个整数,表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8

解题思路

在这里插入图片描述
代码如下

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

const int N=110;
int f[N][N];  //只从前i组物品中选,当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v为体积,w为价值,s代表第i组物品的个数
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];  //读入
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];  //不选
            for(int k=0;k<s[i];k++){
                if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[n][m]<<endl;
}


优化代码

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

const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=0;i<n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以
                if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[m]<<endl;
}


混合背包

这一类型也就是前面所有的总和,分类讨论即可。就不讲解了,直接附上题目及代码。


有 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 <cstdio>
using namespace std;

const int N = 1010, M = 10000;
int f[N], g[N];
int a[M], b[M];
bool c[M]; // false: 完全背包, true: 01背包
int n, m;

int main()
{
    cin >> n >> m;
    int inf = 0;
    for (int i = 0; i < n; i ++)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        if(!s){
            a[inf] = v;
            b[inf ++] = w;
            // c[inf ++] = s;
        }
        else
        {
            if(s == -1) s = 1;
            int k = 1;
            while(k <= s)
            {
                a[inf] = k * v;
                c[inf] = 1;
                b[inf ++] = k * w;
                s -= k;
                k <<= 1;
            }
            if(s)
            {
                a[inf] = s * v;
                c[inf] = 1;
                b[inf ++] = s * w;
            }
        }
    }

    for (int i = 0; i < inf; i ++)
    {
        if(c[i]){
            for (int j = m; j >= a[i]; j --)
                f[j] = max(f[j], f[j - a[i]] + b[i]);
        }
        else{
            for (int j = a[i]; j <= m; j ++)
                f[j] = max(f[j], f[j - a[i]] + b[i]);
        }
    }

    cout << f[m] << endl;

    return 0;
}

最后

阅读完全文希望大家对背包问题有新的理解。若有错的地方可以评论或私信噢。走过路过不要吝啬你的点赞噢。你的支持是我的动力。


本文链接: http://www.dtmao.cc/news_show_200106.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?