- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我有以下向量(或 C 矩阵和 V 向量)和 K1、K2、K3 常量
Constraints [c11 + c12 + c13 + ... + c1n] <= K1
[c21 + c22 + c23 + ... + c2n] <= K2
[c31 + c32 + c33 + ... + c3n] <= K3
-------------------------------------------------
Values [ v1 + v2 + v3 + ... + vn] -> Max
作为输入,我得到 C 和 V 的值,作为输出,我想提供 X 向量,它只包含 0 和 1 值, 给我
[c11 * x1 + c12 * x2 + c13 * x3 + ... + c1n * xn <= K1
[c21 * x1 + c22 * x2 + c23 * x3 + ... + c2n * xn <= K2
[c31 * x1 + c32 * x2 + c33 * x3 + ... + c3n * xn <= K3
------------------------------------------------------
[ v1 * x1 + v2 * x2 + v3 * x3 + ... + vn * xn] -> Max
作为一个过度简化的例子:
输入:
K1 = 15
K2 = 20
K3 = 10
c1 = [3, 6, 8] | sum(c1 * X) <= 15
c2 = [8, 9, 3] | sum(c2 * X) <= 20
c3 = [7, 5, 2] | sum(c3 * x) <= 10
v = [2, 5, 3] | sum( v * X) -> Max
提供 X 向量的输出,该向量最大化约束内的值:
X = [0, 1, 1]
我正在寻找一种优雅的算法(也可以是 Java 或 C# 实现)根据输入提供输出。我们可以假设约束的数量始终为 3,并且提供了 C 和 V(以及 K1、K2、K3)的所有值。
另一个简单的例子可能是:你有一个房间(3D),所以你的约束是房间的宽度、高度和长度房间(K1、K2、K3)并且您有一个家具项目列表(n 项目)。所有 i 件家具都有自己的长度 (c1i)、宽度 (c2i) 和高度 (c3i) 和值 (vi)。您想要用最有值(value)的家具来装点房间,这些家具适合房间的尺寸。所以输出是一个 n 长的 X 变量,它只包含 0 和 1 值,如果 xi = 1,第 i 个元素被选为在房间里,如果 xi = 0 则第 i 个元素不会被选为在房间里。
最佳答案
这是多维 0-1 背包问题,它是 NP 难的。
可以找到解决方法的概述here ,一篇相对较新的研究论文 here和 python
中的遗传算法实现 here .
取自 python 实现(上面的链接 pyeasyga
)是这个例子:
from pyeasyga import pyeasyga
# setup data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
ga = pyeasyga.GeneticAlgorithm(data) # initialise the GA with data
ga.population_size = 200 # increase population size to 200 (default value is 50)
# define a fitness function
def fitness(individual, data):
weight, volume, price = 0, 0, 0
for (selected, item) in zip(individual, data):
if selected:
weight += item[0]
volume += item[1]
price += item[2]
if weight > 12210 or volume > 12:
price = 0
return price
ga.fitness_function = fitness # set the GA's fitness function
ga.run() # run the GA
print ga.best_individual() # print the GA's best solution
data
的最后一个维度是价格,另外两个维度是重量和体积。
您可以调整此示例,使其解决二维以上的问题。
希望对您有所帮助。
编辑:一般而言,遗传算法不能保证找到最优解。对于三个约束,它可能会找到好的解决方案,但不能保证最优。
更新:数学优化解决方案
另一种选择是使用 PuLP ,一个用于数学优化问题的开源建模框架。该框架调用求解器,即专门设计用于解决优化问题的软件。简而言之,框架的工作是将数学问题描述与解决问题时需要的形式联系起来,求解器的工作是实际解决问题。
您可以使用例如 pip
(pip install pulp
) 安装 pulp。
这是前面在 pulp
中建模的示例,通过修改 this示例:
import pulp as plp
# Let's keep the same data
data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195),
(291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145),
(124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312),
(910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100),
(771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120),
(1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153),
(993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)]
w_cap, v_cap = 12210, 12
rng_items = xrange(len(data))
# Restructure the data in dictionaries
items = ['item_{}'.format(i) for i in rng_items]
weight = {items[i]: data[i][0] for i in rng_items}
volume = {items[i]: data[i][1] for i in rng_items}
price = {items[i]: data[i][2] for i in rng_items}
# Make the problem, declare it as a maximization problem
problem_name = "3D Knapsack"
prob = plp.LpProblem(problem_name, plp.LpMaximize)
# Define the variables
plp_vars = plp.LpVariable.dicts('', items, 0, 1, plp.LpInteger)
# Objective function
prob += plp.lpSum([price[i]*plp_vars[i] for i in plp_vars])
# Constraints
prob += plp.lpSum([weight[i]*plp_vars[i] for i in plp_vars]) <= w_cap
prob += plp.lpSum([volume[i]*plp_vars[i] for i in plp_vars]) <= v_cap
# Solution
prob.solve()
# If you want to save the problem formulation in a file
# prob.writeLP(problem_name + 'lp')
# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
print v.name, "=", v.varValue
# The optimised objective function value is printed to the screen
print "Total gain = ", plp.value(prob.objective)
目标是 3,540。
如何运行的演示是 here .
关于algorithm - 基于多约束算法找到最优值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35016448/
滑动窗口限流 滑动窗口限流是一种常用的限流算法,通过维护一个固定大小的窗口,在单位时间内允许通过的请求次数不超过设定的阈值。具体来说,滑动窗口限流算法通常包括以下几个步骤: 初始化:设置窗口
表达式求值:一个只有+,-,*,/的表达式,没有括号 一种神奇的做法:使用数组存储数字和运算符,先把优先级别高的乘法和除法计算出来,再计算加法和减法 int GetVal(string s){
【算法】前缀和 题目 先来看一道题目:(前缀和模板题) 已知一个数组A[],现在想要求出其中一些数字的和。 输入格式: 先是整数N,M,表示一共有N个数字,有M组询问 接下来有N个数,表示A[1]..
1.前序遍历 根-左-右的顺序遍历,可以使用递归 void preOrder(Node *u){ if(u==NULL)return; printf("%d ",u->val);
先看题目 物品不能分隔,必须全部取走或者留下,因此称为01背包 (只有不取和取两种状态) 看第一个样例 我们需要把4个物品装入一个容量为10的背包 我们可以简化问题,从小到大入手分析 weightva
我最近在一次采访中遇到了这个问题: 给出以下矩阵: [[ R R R R R R], [ R B B B R R], [ B R R R B B], [ R B R R R R]] 找出是否有任
我正在尝试通过 C++ 算法从我的 outlook 帐户发送一封电子邮件,该帐户已经打开并记录,但真的不知道从哪里开始(对于 outlook-c++ 集成),谷歌也没有帮我这么多。任何提示将不胜感激。
我发现自己像这样编写了一个手工制作的 while 循环: std::list foo; // In my case, map, but list is simpler auto currentPoin
我有用于检测正方形的 opencv 代码。现在我想在检测正方形后,代码运行另一个命令。 代码如下: #include "cv.h" #include "cxcore.h" #include "high
我正在尝试模拟一个 matlab 函数“imfill”来填充二进制图像(1 和 0 的二维矩阵)。 我想在矩阵中指定一个起点,并像 imfill 的 4 连接版本那样进行洪水填充。 这是否已经存在于
我正在阅读 Robert Sedgewick 的《C++ 算法》。 Basic recurrences section it was mentioned as 这种循环出现在循环输入以消除一个项目的递
我正在思考如何在我的日历中生成代表任务的数据结构(仅供我个人使用)。我有来自 DBMS 的按日期排序的任务记录,如下所示: 买牛奶(18.1.2013) 任务日期 (2013-01-15) 任务标签(
输入一个未排序的整数数组A[1..n]只有 O(d) :(d int) 计算每个元素在单次迭代中出现在列表中的次数。 map 是balanced Binary Search Tree基于确保 O(nl
我遇到了一个问题,但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点,但是当有成千上万的元素时它就不起作用了。 Problem: Say you are given the followin
我有一个列表列表。 L1= [[...][...][.......].......]如果我在展平列表后获取所有元素并从中提取唯一值,那么我会得到一个列表 L2。我有另一个列表 L3,它是 L2 的某个
我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7 4 1 1 1 1 1 4 4 Anwser是2,因为4+4=8 >= 7,
我实行 3 类倒制,每周换类。顺序为早类 (m)、晚类 (n) 和下午类 (a)。我固定的订单,即它永远不会改变,即使那个星期不工作也是如此。 我创建了一个函数来获取 ISO 周数。当我给它一个日期时
假设我们有一个输入,它是一个元素列表: {a, b, c, d, e, f} 还有不同的集合,可能包含这些元素的任意组合,也可能包含不在输入列表中的其他元素: A:{e,f} B:{d,f,a} C:
我有一个子集算法,可以找到给定集合的所有子集。原始集合的问题在于它是一个不断增长的集合,如果向其中添加元素,我需要再次重新计算它的子集。 有没有一种方法可以优化子集算法,该算法可以从最后一个计算点重新
我有一个包含 100 万个符号及其预期频率的表格。 我想通过为每个符号分配一个唯一(且前缀唯一)的可变长度位串来压缩这些符号的序列,然后将它们连接在一起以表示序列。 我想分配这些位串,以使编码序列的预
我是一名优秀的程序员,十分优秀!