前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >动态规划——01背包

动态规划——01背包

作者头像
code-child
发布2023-05-30 11:23:00
1870
发布2023-05-30 11:23:00
举报
文章被收录于专栏:codechild

题目描述

01背包:给你n个物品,每个物品都有一个体积和价值,且物品只有一个,给你一个背包体积v,要求背包里面装的物品价值之和最大。

image.png
image.png

问题求解

对于背包问题,我们都能从下面的思路进行思考: 问题中不是有n个个物件嘛,也就是从0到n个物件中找出体积小于v的最大价值。 我们分解问题,我们从0到i中找小于体积j的最大价值,不包括i,因为问题求的就是包括i的最大价值(后文表示:f(i-1,j)). 而f(i-1,j)是可以求的,怎么求f(i,j)呢?——很简单,去掉第i件物品,那么f(i,j)就可以表示为,f(i-1,j-v[i])+w[i]——v[i]第i件物品的体积 ,w[i]第i件物品的价值。 总结: 最大价值==f(i,j)==f(i-1,j)与f(i-1,j-v[i])+w[i]相比的最大值。

牛客网01背包

代码语言:javascript
复制
cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> v(N+1),w(N+1);
    for(int i=1;i<=N;++i)
        cin>>v[i]>>w[i];
    vector<vector<int>> f;
    f.resize(N+1);
    for(auto& x:f)
        x.resize(V+1);
    //上面都多1个是为了更好的表达
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=V;++j)
        {
            f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
            if(j>=v[i])//说明可能装下这个,如果装的下,他就是最大值,但是不能求出,要进转化
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[N][V]<<endl;
    return 0;
}

优化:

代码语言:javascript
复制
cpp#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> v(N+1),w(N+1);
    for(int i=1;i<=N;++i)
        cin>>v[i]>>w[i];
    vector<int> f;
    f.resize(V+1);
    for(int i=1;i<=N;++i)
    {
        for(int j=V;j>=v[i];--j)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[V]<<endl;
    return 0;
}

优化解释

为什么可以向上面那样优化呢?

  • 因为我们发现都选取不同的i的时候,上一层的空间就是被搁置的,没有被利用的,那么为什么我们不能用上一层的空间呢?

下面主要是解释循环体里面的代码; 之前的代码:

代码语言:javascript
复制
cpp        for(int j=1;j<=V;++j)
        {
            f[i][j]=f[i-1][j];//把前i-1物品的最大值传递给前i物品
            if(j>=v[i])//说明可能装下这个,如果装的下,他就是最大值,但是不能求出,要进转化
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }

我们把2维缩成1维,即只用原来的一行,该行的j列表示从所有的物品中选取不超过j空间大小的最大价值。**记住: **每次内循环完成的时候,表示从i个物品中选取的结果完成

如果这样修改:错误的

代码语言:javascript
复制
cpp    	for(int j=1;j<=V;++j)
        {
            if(j>=v[i])
                f[j]=max(f[j],f[j-v[i]]+w[i]);//这里等价与f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);但是这个公式可能会改变上一层的最大值。
        }

怎么解决呢?倒着来,

代码语言:javascript
复制
cpp        for(int j=V;j>=v[i];--j)//关键是V的问题,才使下面的方程可以进行转换
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);//小括号里面的f[j],是上一层的,但是可以理解为这一层的,把上一层的最大值给给了这一层,后面的参数是这一层的,需要转换。f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-05-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 问题求解
  • 牛客网01背包
    • 优化:
      • 优化解释
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档