我正在开发一个程序来解决0/1背包问题的变体。
原始问题如下所述:https://en.wikipedia.org/wiki/Knapsack_problem.如果将来链接丢失,我会给你一个0/1背包问题的摘要(如果你熟悉它,跳过这一段):假设我们有n
项,每个项都有重量wi
和值vi
。我们想把物品放在一个袋子里,这个袋子支持最大重量W
,这样袋子里的总价值是最大的,而不会加重袋子的重量。项目不能有多个实例(即,我们每个项目只有一个实例)。问题的目标是最大化总和(vi.xi),以便总和(wi.xi)
就我而言,条件和目标都有细微的差异:
>
所有项的权重为1,
wi=1, i=1... n
我总是想把一半的东西放进包里。因此,袋子的最大重量是物品数量的一半(四舍五入)<代码>W=ceil[n/2]
或W=floor[(n 1)/2]
。
此外,袋内重量必须等于其最大容量SUM(wi.xi)=W
最后,我们的目标不是使包内物品的价值最大化,而是使包内物品的价值尽可能接近包外物品的价值。因此,我的目标是minimize | SUM(vi-xi)-SUM[vi(1-xi)]|
,它简化为minimize | SUM[vi(2xi-1)]|
。
现在,在上面的Wikipedia页面中有一个针对原始0/1背包问题的伪代码(您可以在本文底部找到),但我无法将其适应我的场景。有人能帮忙吗?(我不是要代码,只是为了一个想法,所以语言是不相关的)
谢谢!
维基百科针对0/1背包问题的伪代码:
假设w1,w2。。。,wn,W
是严格的正整数。将m[i,w]
定义为使用小于或等于w
的项目(第一个i
项目)可获得的最大值。
我们可以递归地定义m[i, w]
如下:
m[0,w]=0
m[i,w]=m[i-1,w]如果wi
然后可以通过计算
m[n, W]
找到解决方案。
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
for j from 0 to W do:
m[0, j] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i-1] <= j then:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])
else:
m[i, j] := m[i-1, j]
多亏了@harold,这个问题似乎不是背包问题,而是分区问题。我正在寻找的部分伪代码位于相应的Wikipedia页面中:https://en.wikipedia.org/wiki/Partition_problem
编辑:事实上,分区问题算法告诉你一组项目是否可以分成两组相等的值。假设不能,你有近似算法,它说你是否可以把集合分成两个集合,它们的差值小于d
。但是,他们没有告诉你结果的子集,这就是我所寻求的。
我最终在这里找到了一个问题,要求(这里:平衡分区),有一个代码示例,我已经测试过了,工作正常。
我有以下问题: 有一组项目,每个项目有两个不同的正值a和B。 背包有两个值:totalA和totalB。这是所选项目值A和B的最大和。 我必须找出背包能装的最大物品数是多少。 示例: 输入: 总计A:10,总计B:15 项目1 A:3,B:4 项目2 A: 7,B: 2 项目4 A:2,B:1 项目5 A:4,B:6 输出: 3(项目:2、3、4) 如何使用动态规划来解决此任务?
我试图解决一个优化问题,它非常类似于背包问题,但不能用动态规划来解决。我想解决的问题与这个问题非常相似:
我正在写一个程序,以找到最好的MLB阵容使用背包解决方案。为此,我传入球员数据,其中有球员计算的价值和工资。就背包问题而言,工资将是我的“重量”。 我的问题不是能够选择球员,而是选择最优的阵容。我正在选择一个投手,一个中锋,一垒手,二垒手,三垒手,短停,和三个外野手。我可以成功地完成这一切。我希望我的“体重”是36000,但我目前只选择了一个总共21000的阵容。 我是在犯一个公然的错误,我只是没
我目前正在研究一个路由问题(找到一个我想去的地方的子集[每个地方有一定的分数],同时不超过最大的旅行时间),并提出了1/0背包问题的变体,似乎解决了我最初的问题。 根据维基百科,1/0背包被描述为: 给定一组物品,每个物品都有质量和价值,确定集合中每个物品的数量,以便总重量小于或等于给定的限制,总价值尽可能大。 因此,对于每个项目,都有一个固定的重量(质量),当试图解决问题时,可以很容易地使用它,
给定问题: 0/1-背包问题,n个项目的权值为w_i和v_i。求权重加起来为权重W的项目的最大总价值。 但有两个难题: 背包中所有物品的总重量必须正好是w。 项目总量必须为偶数。 我想找到一个算法,同时关注这两个问题。我已经发现了如何一次性关注其中一个。 现在我的问题是如何实现这两个难题一起工作。有办法解决这个吗? (如果我的问题有什么不清楚的地方,尽管问!)
说明 调用方法1: $.f2eAct.myPackage(el,options); 函数说明: 奖品背包 参数说明: 参数名 类型 说明 备注 el string DOM元素对象 必要 act string 活动key 必要 showPage booleam 是否显示页码 默认不显示 pageId int 页面Id 无 pageSize int 每页显示数量 无 filter array 过滤