`
westice
  • 浏览: 115642 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

大概看懂了0-1背包(动态规划)

 
阅读更多

动态规划最泛的思想就是从最小的问题开始,每一步的结果都保存下来,以后更大的结果就直接用小的结果来构造,这样就减少很大的计算量.

我们所要的就是那个最大的结果

 

 

 

 

在解决0-1背包问题中:

两个循环嵌套,一个循环容量(1开始,步长为1),一个循环个数(1开始,步长为1)

 

最佳方案存在一个二维数组里大小为 (最大容量 + 1)*(最大个数 + 1)

第一行和第一列为 0,作为起始条件.

 

 

如果  (本物体价值 出去本物体的剩余空间的最佳方案) > (上一次最佳方案)

   则 本次最佳方案 = (本物体价值 出去本物体的剩余空间的最佳方案)

否则  本次最佳方案 上一次最佳方案

在这之前还要保证本物体的限制条件 

过几天再写个小程序实现,要写作业了.

分享到:
评论

相关推荐

    动态规划解决0-1背包问题

    动态规划是一种有效的算法设计策略,尤其适用于解决具有重叠子问题和最优子结构的问题,而0-1背包问题就是这种策略的一个典型应用。0-1背包问题是一个经典的组合优化问题,它源自实际生活中的资源分配问题,比如在...

    动态规划法求解0-1背包问题实验报告.pdf

    0-1背包问题是一个经典的优化问题,主要涉及动态规划算法的运用。在这个实验报告中,学生使用Java语言解决了一个0-1背包问题的实例。以下是关于这个问题和解决方案的详细解释。 一、问题描述: 0-1背包问题的核心是...

    0-1背包问题(动态规划)

    利用动态规划方法求解经典0-1背包问题,仅供参考,欢迎指正

    动态规划求解0-1背包问题的改进算法完整解释

    动态规划求解0-1背包问题的改进算法完整解释 在计算机算法设计与分析中,动态规划法是解决背包问题的常用方法之一。所谓背包问题,是指在有限的背包容量下,如何选择物品来达到最大价值的问题。在本文中,我们将对...

    0-1背包 动态规划法

    0-1 背包问题动态规划法 动态规划法是解决 0-1 背包问题的一种有效方法,它将问题分解为子问题,递归求解,并将中间结果保存以避免重复计算。该方法可以求解最优解,并且最优解的局部也是最优的。 在 0-1 背包问题...

    C++ 动态规划算法实现0-1背包问题

    在计算机科学中,0-1背包问题是一个经典的动态规划实例,它模拟了如何在一个容量有限的背包中选择物品以最大化价值,而每个物品都有其特定的重量和价值,并且物品要么不被选中(0),要么被完全放入背包(1)。...

    0-1背包问题 动态规划法——C语言代码

    对于0-1背包问题,动态规划的解决方案通常包括以下步骤: 1. 初始化:创建一个二维数组`dp`,其中`dp[i][j]`表示在前`i`件物品中选择总重量不超过`j`的物品所能得到的最大价值。初始化时,`dp[0][j] = 0`,因为没有...

    动态规划法和回溯法求0-1背包问题

    ### 动态规划法与回溯法解决0-1背包问题 #### 一、实验目的与背景 0-1背包问题是一种经典的组合优化问题,在实际应用中有着广泛的用途,例如资源分配、投资组合等问题都可以抽象成背包问题的形式。本实验旨在通过...

    动态规划法解0-1背包问题

    算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考

    动态规划法解决0-1背包问题

    基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]

    0-1背包动态规划回溯法分支限界贪心算法

    本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。

    0-1背包_0-1背包问题_背包算法_背包_

    在"0-1背包.txt"文件中,可能包含了具体的代码示例或更详细的解释,用于阐述如何用回溯法或动态规划实现0-1背包问题的解法。通过阅读和理解这份文件,你可以进一步深化对0-1背包问题的理解,并学习到如何将其应用于...

    0-1背包问题-算法简洁易懂

    解决0-1背包问题的常见算法包括动态规划法和回溯法。在这里,我们将介绍动态规划法。 动态规划法是通过创建一个二维数组dp来解决问题的。其中,dp\[i]\[j]表示前i个物品在容量为j时能得到的最大价值。通过迭代计算...

    0-1背包 动态规划问题详解

    有比较详细的0-1背包动态规划的讲解 有实例可以帮助大家更好的熟悉动态规划问题的理解

    动态规划算法解决0-1背包问题

    在这个场景中,我们关注的是如何使用动态规划来解决0-1背包问题。0-1背包问题是一个经典的组合优化问题,它在很多实际应用中都有体现,比如资源分配、任务选择等。 0-1背包问题的基本描述是这样的:你有一个背包,...

    0-1背包问题 动态规划源码

    动态规划是解决0-1背包问题的一种高效方法。 动态规划的核心思想是将复杂问题分解为相互重叠的子问题,通过存储子问题的解来避免重复计算,从而提高求解效率。在0-1背包问题中,我们可以构建一个二维数组dp,其中dp...

    0-1背包问题

    总之,0-1背包问题是一种重要的算法问题,通过学习和理解其动态规划解决方案,我们可以提升解决问题的能力,并将其应用到实际问题中,如资源分配、任务调度等领域。对于编程爱好者和IT专业人士来说,掌握这类问题的...

    0-1背包算法(动态规划)

    动态规划是解决0-1背包问题的有效方法。动态规划是一种通过将复杂问题分解为子问题来求解的方法,它避免了重复计算,提高了效率。在这个问题中,我们可以构建一个二维数组`dp`,其中`dp[i][j]`表示在前i个物品中选择...

    算法设计动态规划0-1背包

    动态规划是解决0-1背包问题的有效方法。 动态规划是一种通过将大问题分解为相互重叠的小问题来求解的方法。在0-1背包问题中,我们可以用一个二维数组dp来存储子问题的解。dp[i][w]表示在前i个物品中选择总重量不...

    北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java

    北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态...

Global site tag (gtag.js) - Google Analytics