第五章——动态规划1

这篇具有很好参考价值的文章主要介绍了第五章——动态规划1。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

背包问题

01背包问题

有N个·物品和容量是V的背包,每个物品有价值vi和权重(价值)wi属性,每件物品只能用一次(要么用0次,要么用1次),在背包能装得下的情况下,挑一部分物品装入背包,怎样挑才能保证这些物品的价值最大。

第五章——动态规划1
第五章——动态规划1

f(i,j)集合表示所有选法里面的最大值

第五章——动态规划1

f(N,V)表示从前N个物品选,总体积不超过V的集合,状态计算表示的是集合的划分,状态计算是把当前的集合表示成更小的子集,即把当前状态用前面更小的状态表示出来,我们这里采用把f(i,j)所有的选法表示成俩大类,以含i和不含i为划分标准。

划分原则:

  1. 这里划分的时候要做到不重复,即某一个元素不能属于俩个集合,只能属于其中一个。

  1. 不漏,不能漏掉任何一个小的元素(不能让某个元素不属于任何一个集合)

  1. 不漏一定要满足,但是不重有时候可以不用满足。

第五章——动态规划1

左边的集合的特点是从1到i-1中选,并且总体积不超过j。用f(i-1.j)表示.

右边集合的特点是所有从1到i中选,总体积不超过j,可以包含i。

步骤:

  1. 右边的选法里面都包含第i个物品,我们在选择的时候先把每种选法里面的第i个物品都去掉,这个不会影响最大值。

  1. 右边也变成了从i到i-1中选,由于没去掉第i个物品时,总体积不超过j,去掉了第i个物品后,总体积不超过j-vi。右边变成f(i-1,j-vi)

第五章——动态规划1
  1. 选完之后,我们把第i个物品再加回来,右边这种情况的最大价值是f(i-1,j-vi)+wi

第五章——动态规划1
  1. 我们最后将左边和右边价值相比较,取最大值即可

  1. 注意左边集合的这种情况是一定存在的,右边这种情况不一定存在,可能会是空集,当背包体积小于右边vi的时候就是空集。

二维表示

#include<iostream>
#include<algorithm>
using namespace std;
// 01背包问题
const int N = 1010;
int n, m;//n表示物品个数,m表示背包容量
int v[N], w[N];//V表示体积,w表示价值
int f[N][N];  //表示状态
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    //初始化的时候 要计算所有的状态,f[0~n][0~m]是所有的状态
    //f[0][0~m]表示0件物品,总体积不超过0,价值0~m,这样的情况下最大价值是多少,由于一件物品都没选,所以它是0,由于数组会默认是0,我们就不需要初始化
    //因此我们从1开始枚举
    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])//右边这种情况不一定存在
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

一维表示

int f[N];
const int N = 1010;
int n, m;//n表示物品个数,m表示背包容量
int v[N], w[N];//V表示体积,w表示价值
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    //初始化的时候 要计算所有的状态,f[0~n][0~m]是所有的状态
    //f[0][0~m]表示0件物品,总体积不超过0,价值0~m,这样的情况下最大价值是多少,由于一件物品都没选,所以它是0,由于数组会默认是0,我们就不需要初始化
    //因此我们从1开始枚举
    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= v[i]; j--)//一维数组表示的时候,j从0到vi-1的时候是没有意义的,因为下面有这个判断,
            //所以我们直接从m开始,然后这个判断也可以不要
            //从m开始的另一个原因,要保证出现跟f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);一样的效果
        {
            //if (j >= v[i])//右边这种情况不一定存在
                f[j] = max(f[j], f[j - v[i]] + w[i]);
                
        }
    }
    cout << f[m] << endl;
    return 0;
}

完全背包问题

每件物品有无限个。

状态计算和01背包问题有所不同,完全背包问题,状态计算表示的是集合的划分。

该集合表示的是第i个物品选0个,第i个物品选1个,第i个物品选2个,第i个物品选3个,第i个物品选4个……一直到k个,要注意背包的容量,这里最多选K个。

f[i,j]表示前i个物品,总体积不超过j。

0这个子集表示第i个物品不选。等价于只考虑选前i-1个物品,并且总体积不超过j。

用f[i-1,j]来表示。

第五章——动态规划1

我们现在考虑选前i个物品,并且第i个物品选了K个这样选法的集合。

步骤:

  1. 去掉k个物品i,即去掉k个第i个物品

  1. 求max,由于去掉了k个第i个物品,现在变成了max=f[i-1,j-k*v[i]]

  1. 再把去掉的加回来,即+k个物品i

  1. f[i-1,j-k*v[i]]+k*w[i]

f[i,j]=f[i-1,j-v[i]*k]+w[i]*k。

第五章——动态规划1

朴素算法

const int N = 1010;
int n, m;
int v[N],w[N];
int f[N][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 = 0; j <= m; ++j)
            for (int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]*k] + k * w[i]);
    cout << f[n][m] << endl;
    return 0;
}

优化二维算法

把下列式子展开

第五章——动态规划1

橙色部分比红色部分的每一项都多了W

第五章——动态规划1

我们再枚举的时候,枚举俩个状态就可以了,第二个状态在体积满足条件的情况下才可以使用

第五章——动态规划1
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][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=0;j<=m;j++)
      {
        f[i][j] = f[i - 1][j];
        if (j >= v[i])
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }
    cout << f[n][m] << endl;
    return 0;
}

优化一维算法

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=v[i];j<=m;j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

多重背包问题1

多重背包问题,每件物品的个数是有限制的。

跟完全背包相似,根据第i个物品选多少个,把第i个物品分成若干种类

第五章——动态规划1

状态转移方程跟完全背包的朴素算法一样

k从0,1,2一直到s[i]

第五章——动态规划1
第五章——动态规划1
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
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 - v[i] * k] + w[i] * k);
    cout << f[n][m] << endl;
    return 0;
}

多重背包问题2

跟多重背包问题1相比,数据范围变大了,如果直接按多重背包问题1去做,会超时。

我们发现f[i,j-v]后面多了一项。因此,我们不能直接用完全背包的优化方式,来优化这道题

第五章——动态规划1

这里采用二进制的优化方式。

假设某个物品有1023个,s=1023,我们不需要从0枚举到1023,我们可以先把若干个第i个物品打包在一块来考虑,1,2,4,8……512分别代表第一组,第二组,第三组有1,2,4个i物品,即把i物品打包成10组,最多从每组中选1个,然后从选出来的这10个中平凑出0-1023中的任何一个数。

当s=200,我们可以这样打包,最后一组是73,分组规则按照以2为底的质数进行增长,但所有组数加一起的和不能超过某个数的总个数。

第i个物品有s个,我们可以拆分成新的logs组新的物品,新的物品只能用一次。

第五章——动态规划1
第五章——动态规划1

步骤:

  1. 先把第i个物品拆分

  1. 对拆分出来的新的物品,做一遍01背包即可

时间复杂度为

第五章——动态规划1
第五章——动态规划1
const int N = 25000, M = 2010;
int n,m;
int v[N], w[N];
int f[N];
int main()
{
    cin >>n >>m;
    int cnt = 0;//表示所有新的物品
    for (int i = 1; i <= n; i++)
    {
        int a, b, s;//当前物品的体积,价值,个数
        cin >> a >> b >> s;
        int k = 1;//从1开始分
        while (k<=s)
        {
            cnt++;//新物品的编号++
            v[cnt] = a * k;//体积
            w[cnt] = b * k;//价值
            s -= k;
            k *= 2;

        }
        if (s > 0)//此时剩下一些需要补上
        {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;//分组完成
    //做01背包问题即可
    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;
}

分组背包问题

枚举第i组物品,选哪个。

从左到右分别是第i组物品选第0个,第i组物品选第1个……第i组物品选第n个。

第五章——动态规划1

从第i组物品选第k个文章来源地址https://www.toymoban.com/news/detail-427889.html

第五章——动态规划1
第五章——动态规划1
const int N =110 ;
int n, m;
int v[N][N], w[N][N],s[N];//s存每一组的个数
int f[N];
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 = m; j >= 0; j--)//从前往后枚举每一组物品,从大到小枚举所有体积
            for (int k = 0; k < s[i]; k++)//枚举所有选择
                if (v[i][k] <= j)//如果第i组,第k件物品<=j的话,我们才能往下进行,即要注意体积大小
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}

到了这里,关于第五章——动态规划1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 计算机组成原理第五章----存储器容量的扩展与芯片连接

    目录 存储器芯片与CPU的连接 典例 典例二 主存储器容量的扩展与连接方法 位拓展  字拓展  例题 主存大小计算 总结: 1. 确定所需芯片的 数量 (可以通过计算得出) 2. 确定每个芯片的分配地址 (区分最大地址还是最小地址,容量) 3. 确定每个芯片 片选信号CS 的产生方式

    2024年02月11日
    浏览(52)
  • 动态规划之背包问题——完全背包

    算法相关数据结构总结: 序号 数据结构 文章 1 动态规划 动态规划之背包问题——01背包 动态规划之背包问题——完全背包 动态规划之打家劫舍系列问题 动态规划之股票买卖系列问题 动态规划之子序列问题 算法(Java)——动态规划 2 数组 算法分析之数组问题 3 链表 算法

    2024年02月03日
    浏览(55)
  • 完全背包&多重背包问题(动态规划)

    完全背包问题: 每个物品使用次数没有限制,与0-1背包的不同之处在于 遍历背包的顺序 是正序。 多重背包问题: 与完全背包的区别在于,每一种物品是有个数限制的,不能无限选择。这篇博客讲解的非常详细,可以参考学习: 多重背包问题---超详细讲解+优化(不懂你揍我

    2024年04月10日
    浏览(46)
  • 【动态规划专栏】-- 01 背包问题 -- 动态规划经典题型

    目录 背包问题概述 01 背包问题 01背包⭐⭐  【算法原理】 第一问 第二问 C++ 算法代码 复杂度分析 【空间优化 - 滚动数组】 C++ 算法代码 复杂度分析 分割等和子集⭐⭐ 【算法原理】  对于类01背包问题 C++ 算法代码  【空间优化 - 滚动数组】  C++ 算法代码 目标和⭐⭐ 【算

    2024年02月05日
    浏览(54)
  • 动态规划DP之背包问题3---多重背包问题

    目录 DP分析: 优化:  二进制优化 例题:         01背包是每个物品只有一个,完全背包问题是每个物品有无限个。         那么多重背包问题就是 每个物品有有限个 。 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解

    2024年03月20日
    浏览(47)
  • 动态规划-----背包类问题(0-1背包与完全背包)详解

    目录 什么是背包问题? 动态规划问题的一般解决办法: 0-1背包问题: 0 - 1背包类问题  分割等和子集:  完全背包问题:  完全背包类问题 零钱兑换II: 背包问题(Knapsack problem)是一种组合优化的NP完全问题。 问题可以描述为:给定一组物品,每种物品都有自己的重量和价格

    2024年04月17日
    浏览(33)
  • 算法系列--动态规划--背包问题(3)--完全背包介绍

    💕\\\"Su7\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(3)–完全背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(3)--完全背包介绍 链接: 完全背包 可以发现完全背包问题和01背包问题还是特比相似的 分析: 完全背包问题 是 01背包问题 的推广

    2024年04月25日
    浏览(42)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(50)
  • 【动态规划】01背包问题

    动态规划是一种非常常见的算法,不论是在我们平时刷题的过程中还是在竞赛中,总会见到动态规划的身影,而动态规划又分为很多种,其中01背包问题是非常典型的一类动态规划问题。如果大家之前没有了解过动态规划,建议大家先去学习学习动态规划,直接开始01背包问题

    2024年04月15日
    浏览(48)
  • 动态规划——01背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 状态表示 :用一个数组 f[][] (数组可能是一维也可能是二维,根据具体题目具体分析)来表示某个集合,这个集合

    2024年02月03日
    浏览(43)