- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我花了一周的时间编写背包问题的分支定界代码,并且阅读了很多关于该主题的文章和书籍。但是,当我运行我的代码时,我没有得到我期望的结果。从文本文件接收输入,例如:
12
4 1
1 1
3 2
2 3
其中第一行是容量,随后的每一行都是值/权重对。我使用这个文件得到的结果是“8”而不是“10”(除非我弄错了,背包里放不下所有元素)。这是我的代码:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import Queue
from collections import namedtuple
Item = namedtuple("Item", ['index', 'value', 'weight', 'level', 'bound', 'contains'])
class Node:
def __init__(self, level, value, weight, bound, contains):
self.level = level
self.value = value
self.weight = weight
self.bound = bound
self.contains = contains
def upper_bound(u, k, n, v, w):
if u.weight > k:
return 0
else:
bound = u.value
wt = u.weight
j = u.level + 1
while j < n and wt + w[j] <= k:
bound += v[j]
wt += w[j]
j += 1
# fill knapsack with fraction of a remaining item
if j < n:
bound += (k - wt) * (v[j] / w[j])
return bound
def knapsack(items, capacity):
item_count = len(items)
v = [0]*item_count
w = [0]*item_count
# sort items by value to weight ratio
items = sorted(items, key=lambda k: k.value/k.weight, reverse = True)
for i,item in enumerate(items, 0):
v[i] = int(item.value)
w[i] = int(item.weight)
q = Queue.Queue()
root = Node(0, 0, 0, 0.0, [])
root.bound = upper_bound(root, capacity, item_count, v, w)
q.put(root)
value = 0
taken = [0]*item_count
best = set()
while not q.empty():
c = q.get()
if c.bound > value:
level = c.level+1
# check 'left' node (if item is added to knapsack)
left = Node(c.value + v[level], c.weight + w[level], level, 0.0, c.contains[:])
left.contains.append(level)
if left.weight <= capacity and left.value > value:
value = left.value
best |= set(left.contains)
left.bound = upper_bound(left, capacity, item_count, v, w)
if left.bound > value:
q.put(left)
# check 'right' node (if items is not added to knapsack)
right = Node(c.value, c.weight, level, 0.0, c.contains[:])
right.contains.append(level)
right.bound = upper_bound(right, capacity, item_count, v, w)
if right.bound > value:
q.put(right)
for b in best:
taken[b] = 1
value = sum([i*j for (i,j) in zip(v,taken)])
return str(value)
我的索引关闭了吗?我没有正确遍历树或计算边界吗?
最佳答案
def upper_bound(u, k, n, v, w):
if u.weight > k:
return 0
else:
bound = u.value
wt = u.weight
j = u.level
while j < n and wt + w[j] <= k:
bound += v[j]
wt += w[j]
j += 1
# fill knapsack with fraction of a remaining item
if j < n:
bound += (k - wt) * float(v[j])/ w[j]
return bound
def knapsack(items, capacity):
item_count = len(items)
v = [0]*item_count
w = [0]*item_count
# sort items by value to weight ratio
items = sorted(items, key=lambda k: float(k.value)/k.weight, reverse = True)
for i,item in enumerate(items, 0):
v[i] = int(item.value)
w[i] = int(item.weight)
q = Queue.Queue()
root = Node(0, 0, 0, 0.0,[])
root.bound = upper_bound(root, capacity, item_count, v, w)
q.put(root)
value = 0
taken = [0]*item_count
best = set()
while not q.empty():
c = q.get()
if c.bound > value:
level = c.level+1
# check 'left' node (if item is added to knapsack)
left = Node(level,c.value + v[level-1], c.weight + w[level-1], 0.0, c.contains[:])
left.bound = upper_bound(left, capacity, item_count, v, w)
left.contains.append(level)
if left.weight <= capacity:
if left.value > value:
value = left.value
best = set(left.contains)
if left.bound > value:
q.put(left)
# check 'right' node (if items is not added to knapsack)
right = Node(level,c.value, c.weight, 0.0, c.contains[:])
right.bound = upper_bound(right, capacity, item_count, v, w)
if right.weight <= capacity:
if right.value > value:
value = right.value
best = set(right.contains)
if right.bound > value:
q.put(right)
for b in best:
taken[b-1] = 1
value = sum([i*j for (i,j) in zip(v,taken)])
return str(value)
关于Python 背包分支定界法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22310474/
我已经用 Scala 中的每一项编写了有界背包问题的答案,并尝试将其转换为 Haskell,结果如下: knapsack :: [ ( Int, Int ) ] -> [ ( Int, Int ) ]
我正在解决这个动态编程问题,并且我一直坚持用 Java 编写迭代解决方案 目标是找到花费 X 美分所需的最少卡路里数。如果我们不能恰好花费 X 美分,那么就没有解决方案。我们给定了 N 个元素,每个元
根据维基百科和我浏览过的其他资源,您需要矩阵m[n][W]; n - 元素数量和 W - 背包的总容量。这个矩阵变得非常大,有时大到无法在 C 程序中处理。我知道动态规划的基础是节省内存时间,但是,有
我发现此代码使用蛮力机制解决背包问题(这主要是为了学习,因此无需指出动态更有效)。我得到了可以工作的代码,并且了解了大部分代码。最多。这是问题: 我注意到这两个条件,我不知道它们如何工作以及为什么在代
我必须实现背包问题的以下变体。背包中的每件元素都有优先级和重量。现在我指定一个权重 X。我必须知道计算权重总和至少为 X 并且具有最低优先级的最小项目集。每个项目只能选择一次。示例: Knap
所以我想知道如何计算背包问题的所有解。也就是说,我有兴趣从一组最大大小为 K 的数字中找出可能的子集数。 例如,我们有一组大小为 {3, 2, 5, 6, 7} 的项目,最大大小为 K = 13。因此
我在执行任务时遇到了问题。我有一个数据库,其中包含所有具有“价格”值的项目。它们连接到不同的“轮次”,“轮次”有一个“总值(value)”,其中这些项目“价格”-值(value)全部放在一起定义了“总
我遇到的问题如下: 给定一个包含 N 个元素的队列,每个元素都有一个重量,以及一个包含 K 个容器的队列。我们需要按照元素来的顺序将元素分成容器。例如,第一个项目只能进入第一个容器,第二个可以进入第一
问题如下: You have n trip lengths in km which should be divided among m number of days such that the max
我昨晚在开发一个应用程序时遇到了一个特定的问题,我确信它可能有一个有效的算法来解决它。谁能推荐一下? 问题: TL;DR:也许图片会有所帮助:http://www.custom-foam-insert
如何获取下拉列表,其中占位符显示“选择类别”作为默认选择? 以下代码没有渲染占位符 $this->crud->addField([ // Select2 'label'
刚刚带背包的新品。我在官方网站上搜索并用谷歌搜索,但没有找到答案 在 laravel 7 中,使用 Backpack 4.1 我的数据模型是:客户有很多地址 关系在客户模型中配置: public fu
据我所知(如果我错了请纠正我),背包只处理 $fillable 字段。整个 laravel 的事情不就是 $fillable 和 $guarded 之间的分离吗? MWE: 在 User.php 中:
看到this之后讲座我创建了以下背包代码。在讲座中,教授说从最优值(19:00 分钟)确定集合很容易,但我找不到如何去做。我在代码中提供了一个将值相加为 21 的示例,我如何根据该值确定集合(在本例中
为什么贪心法适用于连续背包问题而不适用于 0-1 背包问题? 最佳答案 对于连续背包,在最佳解决方案中,您不能有 q > 0 的每单位成本为 c 的元素,同时留下 q' > 0 成本为 c' > c
我在理解动态规划时遇到了一些困难,尽管我已经通读了很多资源试图理解。 我理解使用斐波那契算法给出的动态规划示例。我明白如果你使用分而治之的方法,你最终会多次解决一些子问题,而动态编程通过解决这些重叠的
假设一个经典的 0-1 背包问题,但您可以上溢/下溢背包并受到一些惩罚。每单位溢出(重量超过最大容量)扣除X利润,每单位下溢(重量低于最大容量)扣除Y利润。 我想按利润与重量的比率对所有元素进行排序,
我正在编写具有多个约束的背包 0-1 的变体。除了重量限制外,我还有数量限制,但在这种情况下,我想解决背包问题,因为我的背包中需要恰好有 n 件元素,重量小于或等于 W。我我目前正在为基于 Roset
给定一个无限正整数数组或一个正整数流,找出总和为 20 的前五个数。 通过阅读问题陈述,它首先似乎是 0-1 Knapsack 问题,但我很困惑 0-1 Knapsack algo 可以在流上使用的整
我想解决一个3维背包问题。 我有许多不同宽度、高度、长度和值(value)的盒子。我有一个指定的空间,我想把盒子放在那个空间里,这样我就能获得最优的利润。我想使用暴力来做到这一点。 我正在用 Java
我是一名优秀的程序员,十分优秀!