最近看了下背包问题的算法。顺便用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
}
}
效率可能不是最优(递归会消耗堆栈)的,但还算直观。
分享到:
相关推荐
0-1背包问题是一种经典的组合优化问题,在计算机科学和运筹学中有着广泛的应用。它描述的是这样的场景:你有一组物品,每件物品都有一个重量和价值,你需要选择一部分物品放入容量有限的背包中,使得背包中的物品总...
《基于MATLAB的遗传算法在背包问题中的应用》 背包问题是一种典型的组合优化问题,广泛存在于资源分配、项目选择等领域。在本项目中,我们利用MATLAB强大的计算能力,结合遗传算法,对背包问题进行了有效的求解,以...
背包问题根据其约束条件可以分为0-1背包问题、完全背包问题和多重背包问题。 **0-1背包问题**是最基础的形式,每种物品只能取或不取,不能分割。在Matlab中求解0-1背包问题,通常采用动态规划(Dynamic Programming...
《背包问题九讲》,dd_engi大神...目录:1、01背包问题;2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略,希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型,在...
这里我们关注的是一个经典的数据结构问题——背包问题。背包问题是一类优化问题,常见于运筹学、计算机科学和算法设计中。在本案例中,我们将讨论如何用C语言和栈来解决这类问题。 首先,让我们了解背包问题的基本...
### 背包问题九讲2.0(13年修订版) #### 一、01背包问题 **1.1 题目** 给定N件物品和一个容量为V的背包,每件物品有一个固定的费用\( C_i \)和价值\( W_i \)。目标是从这些物品中选择若干件放入背包,使得背包内...
在解决背包问题时,贪心算法的应用尤为常见,尤其是对于部分背包问题。 0-1背包问题是最基础的形式,其中每个物品要么完全放入背包,要么完全不放。但在部分背包问题中,我们可以选择物品的一部分进行装入,这样...
背包问题有许多变种,例如完全背包问题、多重背包问题、混合三种背包问题、二维费用的背包问题、分组的背包问题、有依赖的背包问题等。这些变种问题通常在物品的限制条件、背包的限制条件或者物品的价值函数等方面...
算法设计与分析实验之背包问题 背包问题是计算机科学中的一种经典问题,属于组合优化问题。该问题的目标是从给定的物品集中选择一部分物品,以使得背包的价值最大化,而不超过背包的容量限制。 在给定的源代码中,...
### 背包问题详解及变种解析 #### 一、引言 背包问题作为计算机科学与算法领域中的经典问题之一,在实际应用中具有广泛的意义。它不仅涉及到动态规划的核心思想,而且通过不同的变种形式,能够帮助我们深入理解...
【背包问题可视化】是一种在计算机科学中用于解决优化问题的经典算法,主要应用于资源分配和决策制定。这个项目是基于.NET框架实现的,并且利用ASP.NET技术进行可视化展示。通过使用`asp:table`控件,开发者创建了一...
【背包问题】是一种经典的组合优化问题,广泛应用于资源分配、任务调度等领域。在这个问题中,我们有一个容量有限的背包和一系列物品,每件物品都有一个重量和价值。目标是在不超过背包容量的前提下,选择物品以最大...
在IT领域,优化问题是一个广泛的研究方向,其中背包问题是经典的组合优化问题之一。"禁忌搜索背包问题"是指利用禁忌搜索算法来寻找背包问题的最优解。在这个问题中,我们有一个固定容量的背包,以及一系列物品,每件...
0-1背包问题是一种经典的计算机科学中的组合优化问题,它源于实际生活中的资源分配问题,例如在有限的容量下选择最有价值的物品进行携带。在这个问题中,我们有一组物品,每种物品都有一个重量和一个价值,目标是...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
标题中的“背包问题数据集”指的是在运筹学和计算机科学领域中常见的一种优化问题,称为背包问题(Knapsack Problem)。这个问题的基本形式是:给定一组物品,每种物品都有一个重量和一个价值,目标是在不超过给定...
【标题】"背包问题PSO算法代码"涉及的是在计算机科学和优化技术中的经典问题——背包问题,结合了粒子群优化(PSO)算法来寻找解决方案。粒子群优化是一种受到鸟类群体行为启发的全局优化算法,它通过模拟群体中个体...
01背包问题是一种经典的计算机科学优化问题,常用于求解有限资源下的最佳分配策略。它在实际生活中的应用广泛,比如商品装箱、任务调度、投资组合优化等场景。在这个问题中,我们有一系列物品,每个物品都有一个价值...
本项目中,遗传算法被应用于解决经典的背包问题,这是一种典型的组合优化问题。在背包问题中,我们通常有一组物品,每件物品都有一个重量和价值,目标是在不超过背包总容量的前提下,选取物品以最大化总价值。 首先...