动态规划:完全背包问题

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

ACwing #3. 完全背包问题

动态规划:完全背包问题

完全背包问题和01背包问题很相似。
01背包问题每个物品只能选一个,而完全背包问题每个物品可以选无限次。

DP问题的关键是找到状态转移方程:

①定义f[i][j]表示从前 i 个物品中选择,体积为 j 的时候的最大价值。
②那么转移方程f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]],f[i - 1][j - 2 * v[i]],.....,f[i - 1][j - k * v[i]],....)

因此代码就是:

#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 ++)
    {
        scanf("%d%d",&v[i],&w[i]);
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = 1 ; 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]);
    }

    printf("%d",f[n][m]
    return 0;
}

由于数据量级的原因,此代码肯定会发生TLE,因此需要进行优化。

f[i , j ] = max( f[i-1,j] , f[i- 1,j - v[i]+ w[i] ,  f[i - 1,j-2 * v[i]]+2 * w[i] , f[i -1,j - 3 * v[i]]+3 * w[i] , .....)
f[i , j - v[i]]= max(       f[i - 1,j - v[i]] ,         f[i - 1,j - 2 * v[i]] + w[i] , f[i - 1,j- 3 * v[i]]+2 * w[i] , .....)

由上两式,可得出如下递推关系: 
                        f[i][j]=max(f[i, j - v[i] ] + w[i] , f[i - 1][j])  

因此优化后的代码变为:

#include <iostream>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  
  for(int i = 1;i <= n;i++){
      scanf("%d%d",&v[i],&w[i]);
  } 
  for(int i = 1;i <= n;i++)
    for(int j = 1;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]);
    }
    
  printf("%d",f[n][m]);
  return 0;
}

        可以看出代码与01背包非常相似,因此尝试能否做进一步优化。

优化完成后的状态转移方程:f[j] = max(f[j], f[j - v[i]] + w[i]) 

代码如下:文章来源地址https://www.toymoban.com/news/detail-418149.html

#include <iostream>
using namespace std;

const int N=1010;
int v[N],w[N],f[N];
int n,m;

int main()
{
  scanf("%d%d",&n,&m);  
  for(int i = 1;i <= n;i++){
      scanf("%d%d",&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]);
    }    
  printf("%d",f[m]);  
  return 0;
}

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

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

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

相关文章

  • 动态规划之背包问题——完全背包

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

    2024年02月03日
    浏览(53)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(46)
  • 【动态规划之完全背包问题】完全背包问题的通用解法与优化

    ⭐️ 前面的话 ⭐️ 本篇文章将介绍动态规划中的背包问题——完全背包问题,前面我们已经介绍了0-1背包问题,其实完全背包问题就只改了0-1背包问题的一个条件,即物品可选择次数由一次改为无数次,仅此而已,下面我们就来开始介绍完全背包问题。 📒博客主页:未见

    2023年04月22日
    浏览(45)
  • 动态规划:完全背包问题

    ACwing #3. 完全背包问题 完全背包问题和01背包问题很相似。 01背包问题每个物品只能选一个,而完全背包问题每个物品可以选无限次。 DP问题的关键是找到状态转移方程: ①定义f[i][j]表示从前 i 个物品中选择,体积为 j 的时候的最大价值。 ②那么转移方程f[i][j] = max(f[i - 1][j

    2023年04月19日
    浏览(42)
  • 动态规划——完全背包问题

    由于本人实力尚浅,接触算法没多久,写这篇blog仅仅是想要提升自己对算法的理解,如果各位读者发现什么错误,恳请指正,希望和大家一起进步。(●’◡’●) 了解完全背包问题前可以先去看看01背包问题(良心正解),先了解这个基础问题会更有利于你了解下面的完全背

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

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

    2024年04月25日
    浏览(41)
  • 动态规划完全背包问题-java

    完全背包问题跟01背包问题思路大致一样,只不过对于物品的拿取次数不在限制,我们只需要考虑这点即可。 文章目录 前言 一、什么是完全背包问题? 二、问题模拟 1.样例数据 2.算法思路 三、代码如下 1.代码如下(示例): 2.读入数 3.代码运行结果 总结 完全背包问题跟

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

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

    2024年04月17日
    浏览(33)
  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(48)
  • 力扣刷题-动态规划算法3:完全背包问题

    问题描述: 1)有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 2) 每件物品都有无限个(也就是可以放入背包多次) (比0-1背包多出的条件) 3) 求解将哪些物品装入背包里物品价值总和最大。 求解步骤: 1)首先遍历物品,然

    2023年04月13日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包