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

背包问题

阅读更多

最近看了下背包问题的算法。顺便用scala写了下简单的实现

 

问题概述:现有一个只能承受limit重量的背包,放入一些物品,物品的重量和价值在List[(Int,Int)]中,如何是背包中物品最大价值

 

 

def bag(item: List[(Int, Int)], limit: Int): Int = item match {
    case (weight, value) :: tail if (limit > 0 && limit >= weight) => 
      math.max(bag(tail, limit), value + bag(tail, limit - weight))
    case _ => 0
  }

 

 

如果是求怎么组合。List[(Int,Int,Int)]表示(id,weight,value)的列表

 

 

 def bag1(items: List[(Int, Int, Int)])(limit: Int): List[(Int, Int, Int)] = {
    def valueOf(x: List[(Int, Int, Int)]) =
      x.foldLeft(0)((sum, item) => sum + item._3)
    def greater(left: List[(Int, Int, Int)], right: List[(Int, Int, Int)]) =
      if (valueOf(left) > valueOf(right)) left else right
    items match {
      case (id, weight, value) :: tail if limit >= weight && limit > 0 =>
        greater(bag1(tail)(limit), (id, weight, value) :: bag1(tail)(limit - weight))
      case _ => Nil
    }
  }

 

效率可能不是最优(递归会消耗堆栈)的,但还算直观。

分享到:
评论

相关推荐

    matlab程序(解决0-1背包问题).zip_背包_背包算法 matlab_背包问题_遗传算法 背包_遗传算法背包

    0-1背包问题是一种经典的组合优化问题,在计算机科学和运筹学中有着广泛的应用。它描述的是这样的场景:你有一组物品,每件物品都有一个重量和价值,你需要选择一部分物品放入容量有限的背包中,使得背包中的物品总...

    背包问题.rar_matlab算法实现背包问题_价值背包算法_背包最大价值_背包问题_遗传算法 背包

    《基于MATLAB的遗传算法在背包问题中的应用》 背包问题是一种典型的组合优化问题,广泛存在于资源分配、项目选择等领域。在本项目中,我们利用MATLAB强大的计算能力,结合遗传算法,对背包问题进行了有效的求解,以...

    背包问题 Matlab 求解

    背包问题根据其约束条件可以分为0-1背包问题、完全背包问题和多重背包问题。 **0-1背包问题**是最基础的形式,每种物品只能取或不取,不能分割。在Matlab中求解0-1背包问题,通常采用动态规划(Dynamic Programming...

    背包问题九讲2.0最新版

    《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;

    贪心算法 背包问题 c语言

    ### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...

    经典数据结构问题 背包问题所有解

    这里我们关注的是一个经典的数据结构问题——背包问题。背包问题是一类优化问题,常见于运筹学、计算机科学和算法设计中。在本案例中,我们将讨论如何用C语言和栈来解决这类问题。 首先,让我们了解背包问题的基本...

    背包问题九讲2.0(13年修订版).pdf

    ### 背包问题九讲2.0(13年修订版) #### 一、01背包问题 **1.1 题目** 给定N件物品和一个容量为V的背包,每件物品有一个固定的费用\( C_i \)和价值\( W_i \)。目标是从这些物品中选择若干件放入背包,使得背包内...

    贪心算法 背包问题 C语言

    在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础的形式,其中每个物品要么完全放入背包,要么完全不放。但在部分背包问题中,我们可以选择物品的一部分进行装入,这样...

    背包问题九讲 2.0 RC1

    背包问题有许多变种,例如完全背包问题、多重背包问题、混合三种背包问题、二维费用的背包问题、分组的背包问题、有依赖的背包问题等。这些变种问题通常在物品的限制条件、背包的限制条件或者物品的价值函数等方面...

    算法设计与分析实验之背包问题

    算法设计与分析实验之背包问题 背包问题是计算机科学中的一种经典问题,属于组合优化问题。该问题的目标是从给定的物品集中选择一部分物品,以使得背包的价值最大化,而不超过背包的容量限制。 在给定的源代码中,...

    背包问题,详细讲解几种背包问题

    ### 背包问题详解及变种解析 #### 一、引言 背包问题作为计算机科学与算法领域中的经典问题之一,在实际应用中具有广泛的意义。它不仅涉及到动态规划的核心思想,而且通过不同的变种形式,能够帮助我们深入理解...

    背包问题可视化

    【背包问题可视化】是一种在计算机科学中用于解决优化问题的经典算法,主要应用于资源分配和决策制定。这个项目是基于.NET框架实现的,并且利用ASP.NET技术进行可视化展示。通过使用`asp:table`控件,开发者创建了一...

    背包问题的贪心法C语言实现

    【背包问题】是一种经典的组合优化问题,广泛应用于资源分配、任务调度等领域。在这个问题中,我们有一个容量有限的背包和一系列物品,每件物品都有一个重量和价值。目标是在不超过背包容量的前提下,选择物品以最大...

    禁忌搜索背包问题,禁忌搜索算法解决背包问题,matlab

    在IT领域,优化问题是一个广泛的研究方向,其中背包问题是经典的组合优化问题之一。"禁忌搜索背包问题"是指利用禁忌搜索算法来寻找背包问题的最优解。在这个问题中,我们有一个固定容量的背包,以及一系列物品,每件...

    0-1背包问题

    0-1背包问题是一种经典的计算机科学中的组合优化问题,它源于实际生活中的资源分配问题,例如在有限的容量下选择最有价值的物品进行携带。在这个问题中,我们有一组物品,每种物品都有一个重量和一个价值,目标是...

    背包问题 数学建模 背包问题 数学建模

    背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法

    背包问题数据集

    标题中的“背包问题数据集”指的是在运筹学和计算机科学领域中常见的一种优化问题,称为背包问题(Knapsack Problem)。这个问题的基本形式是:给定一组物品,每种物品都有一个重量和一个价值,目标是在不超过给定...

    背包问题PSO算法代码

    【标题】"背包问题PSO算法代码"涉及的是在计算机科学和优化技术中的经典问题——背包问题,结合了粒子群优化(PSO)算法来寻找解决方案。粒子群优化是一种受到鸟类群体行为启发的全局优化算法,它通过模拟群体中个体...

    01背包问题的C语言代码

    01背包问题是一种经典的计算机科学优化问题,常用于求解有限资源下的最佳分配策略。它在实际生活中的应用广泛,比如商品装箱、任务调度、投资组合优化等场景。在这个问题中,我们有一系列物品,每个物品都有一个价值...

    遗传算法解决背包问题

    本项目中,遗传算法被应用于解决经典的背包问题,这是一种典型的组合优化问题。在背包问题中,我们通常有一组物品,每件物品都有一个重量和价值,目标是在不超过背包总容量的前提下,选取物品以最大化总价值。 首先...

Global site tag (gtag.js) - Google Analytics