是否有更好的方法来猜测可能的未知变量而不是蛮力而不是我在做什么？机器学习？
Los*_*oul 29 python algorithm machine-learning neural-network tensorflow
我有一个符合以下规则的游戏:
用户获得水果价格并且每次都有机会在他们的水果篮中购买或出售物品.
一次转动,用户的篮子总变化不会超过10%.
- 水果价格每天都在变化,当乘以水果篮中的物品数量时,篮子的总价值也会相对于每天的水果价格变化而变化.
- 该计划仅给出所有水果的当前价格和篮子的当前价值(水果的当前价格*篮子中所有项目的数量).
- 根据这2个输入(所有水果价格和篮子总价值),该程序试图猜测篮子中的物品.
- 一个篮子不能容纳超过100件物品但是空位可以是空的
- 玩家可以多次转弯.
我的目标是尽可能以低廉的价格准确地猜测(如果没有蛮力),并且如果有数以千计的新果实,则进行扩展.
我很难找到答案,但在我看来,并不难.如果我有下表.我可以在第1天学习并获得以下数据:
Apple 1
Pears 2
Oranges 3
Basket Value = 217
我可以做一个餐巾计算的背面并假设,篮子里的重量是:0苹果,83个梨和17个橙子等于篮子值217.
第二天,水果和篮子的价值发生了变化.To(apple = 2,Pear 3,Oranges 5),篮子值为348.当我假设体重超过(0,83,17)时,我得到的总值为334 - 不正确!通过我的脚本运行这个,我看到最接近的匹配是0苹果,76个梨,24个橙子,虽然它们等于348,当它的因素变化百分比是38%变化所以它是不可能的!
我知道我可以完全暴力,但如果我有1000个水果,它将无法扩展.不要跳过任何潮流,但像神经网络这样的东西可以迅速排除不太可能,所以我计算大量的数据？我认为他们必须比纯暴力更具可扩展性/更快速的方式？或者是否有任何其他类型的解决方案可以获得结果？
这是原始数据(记住程序只能看到价格和总篮数值):
这里有一些暴力代码(谢谢@paul Hankin比我的更清洁的例子):
def possibilities(value, prices):
for i in range(0, value+1, prices[0]):
for j in range(0, value+1-i, prices[1]):
k = value - i - j
if k % prices[2] == 0:
yield i//prices[0], j//prices[1], k//prices[2]
def merge_totals(last, this, r):
ok = []
for t in this:
for l in last:
f = int(sum(l) * r)
if all(l[i] -f <= t[i] <= l[i] + f for i in range(len(l))):
ok.append(t)
break
return ok
days = [
(217, (1, 2, 3)),
(348, (2, 3, 5)),
(251, (1, 2, 4)),
]
ps = None
for i, d in enumerate(days):
new_ps = list(possibilities(*d))
if ps is None:
ps = new_ps
ps = merge_totals(ps, new_ps, 0.10)
print('Day %d' % (i+1))
for p in ps:
print('Day %d,' % (i+1), 'apples: %s, pears: %s, oranges: %s' % p)
print
更新 - 到目前为止的信息非常棒.将问题分解为两个问题是否有意义？一个是产生可能性,而另一个是找到可能性之间的关系(每日变化不超过10%).通过排除可能性,难道也不能用它来帮助只产生可能的可能性,首先？我不确定这种方法是否仍然存在,但我确实感到两种问题都不同但紧密相关.你的意见？
更新2 - 关于%变化有很多问题.这是可以更改的篮子中的项目总量.为了使用游戏示例,想象一下商店说 - 你可以出售/退货/购买水果,但它们不能超过你最后账单的10%.因此,虽然水果价格的变化会导致您的购物篮价值发生变化,但用户不能采取任何影响它的行动超过10%.因此,如果值为100,他们可以进行更改,将其创建为110但不会更多.
pkp*_*pnd 27
我讨厌让你失望,但我真的不认为神经网络会对这个问题有所帮助,IMO对你的问题的最佳答案就是建议"不要浪费你的时间去尝试神经网络".
决定神经网络是否适用的一个简单的经验法则是,"一般成年人能在几秒钟内合理地解决这个问题吗？" 对于诸如"此图像中的内容","回答此问题"或"转录此音频剪辑"等问题,答案是肯定的.但是,对于您的问题,答案是最明确的没有.
神经网络存在局限性,其中一个原因是它们不能很好地处理高度逻辑问题.这是因为答案通常不"平稳".如果您拍摄图像并稍微更改一些像素,则图像的内容仍然相同.如果您采用音频剪辑并插入几毫秒的噪音,神经网络可能仍然能够弄清楚所说的内容.但在你的问题中,将一天的"总篮子价值"改变一个单位,你的答案将会大幅改变.
似乎解决问题的唯一方法是使用"经典"算法.如目前所述,可能没有比蛮力更好的算法,并且可能无法排除太多.例如,如果每天都有所有水果价格相同的财产怎么办？每个水果的数量可以变化,只要水果的总数是固定的,因此可能性的数量仍然是水果数量的指数.如果您的目标是"生成可能性列表",那么没有算法可以比指数时间更好,因为在某些情况下此列表可能会指数级大.
有趣的是,您的部分问题可以简化为整数线性程序(ILP).考虑一个单一的一天,在这里您将得到篮总B与每个水果的成本c_i,对于i=1通过i=n(如果n是不同水果的总数).假设价格很大,所以你可以用单位成本水果"填满"篮子并不明显.在这种情况下甚至可能很难找到单一的解决方案.配方为ILP,这相当于找到这样的整数值x_i:
sum_i (x_i*c_i) = x_1*c_1 + x_2*c_2 + ... + x_n*c_n = B
并且x_i >= 0为所有人1 <= i <= n(不能有负面的果实)和sum_i x_i <= 100(最多可以有100个水果).
好消息是存在合适的ILP求解器 - 您可以直接移交上述公式,解算器将尽力找到单个解决方案.您甚至可以添加一个"目标函数",求解器将最大化或最小化 - 最小化可以最大限度地减少sum_i x_i篮子中水果的总数.坏消息是ILP是NP完全的,因此几乎没有希望找到大量水果的有效解决方案(等于变量的数量x_i).
我认为最好的方法是尝试ILP方法,但也会对场景引入更多限制.例如,如果所有水果的素数成本不同,该怎么办？这有一个很好的属性,如果你找到一个解决方案,你可以枚举一堆其他相关的解决方案.如果一个苹果成本m和橙色成本n,在哪里m和n相对黄金,那么你可以"交易" n*x苹果m*x橙子而不改变篮子总数,任何整数x>0(只要你有足够的苹果和橙子开始).如果您选择所有水果具有不同的素数成本,那么所有成本将成对相对素数.我认为这种方法会导致某一天的解决方案相对较少.
您还可以考虑其他约束,例如"篮子中不能有超过5种单一果实"(添加约束x_i <= 5),或者"篮子中最多可以有5种不同的果实"(但这很难编码为ILP约束).添加这些约束将使ILP求解器更容易找到解决方案.
当然,上面的讨论集中在一天,你有多天的数据.如果问题中最困难的部分是在任何一天找到任何解决方案(如果你的价格很高就会发生这种情况),那么使用ILP解算器会给你一个很大的提升.如果很容易找到解决方案(如果你有一个非常低成本的水果可以"填满"你的篮子,就会发生这种情况),而问题中最难的部分是找到多天内"一致"的解决方案,那么ILP方法可能不是最合适的,一般来说这个问题似乎更难以推理.
编辑:并且如评论中所述,对于"10%更改"约束的某些解释,您甚至可以将整个多日问题编码为ILP.
在我看来,你的方法是合理的,但它是否取决于实际游戏中数字的大小.这是一个比你更有效的完整实现(但仍有很大的改进空间).它保留前一天的可能性列表,然后将当前日期数量过滤到前一天可能性的5%以内,并将其打印出来.
def possibilities(value, prices):
for i in range(0, value+1, prices[0]):
for j in range(0, value+1-i, prices[1]):
k = value - i - j
if k % prices[2] == 0:
yield i//prices[0], j//prices[1], k//prices[2]
def merge_totals(last, this, r):
ok = []
for t in this:
for l in last:
f = int(sum(l) * r)
if all(l[i] -f <= t[i] <= l[i] + f for i in range(len(l))):
ok.append(t)
break
return ok
days = [
(26, (1, 2, 3)),
(51, (2, 3, 4)),
(61, (2, 4, 5)),
]
ps = None
for i, d in enumerate(days):
new_ps = list(possibilities(*d))
if ps is None:
ps = new_ps
ps = merge_totals(ps, new_ps, 0.05)
print('Day %d' % (i+1))
for p in ps:
print('apples: %s, pears: %s, oranges: %s' % p)
print
问题框架
该问题可以描述为组合优化问题.您正在尝试从有限的一组对象(水果项的所有可能组合)中找到最佳对象(水果项的组合).通过适当的类比和转换,我们可以将这个水果篮问题减少到众所周知的,并且广泛研究(自1897年以来)背包问题.
解决这类优化问题是NP难的.回答的问题是"我们能找到价值为X的水果商品的组合吗？" 是NP完全的.由于您想要考虑最糟糕的情况,当您有数以千计的水果项目时,最好的办法是使用元启发式算法,如进化计算.
提出的解决方案
进化计算是一系列受生物启发的元启发式算法.他们通过修改和混合(演化)基于适应度函数的最合适的候选解决方案并在多次迭代中丢弃最不合适的候选解决方案来工作.解决方案的适用性越高,它就越有可能再现类似的解决方案并生存到下一代(迭代).最终,找到了本地或全局最优解决方案.
当搜索空间太大而无法覆盖传统的闭合形式数学解时,这些方法提供了所需的折衷.由于这些算法的随机性质,算法的不同执行可能导致不同的局部最优,并且不能保证将找到全局最优.由于我们有多个有效的解决方案,因此在我们的案例中赔率很高.
例
让我们使用Python中的分布式进化算法(DEAP) 框架,并将他们的背包问题示例改进到我们的问题中.在下面的代码中,我们对包含100多个项目的篮子应用强烈惩罚.这将严重降低他们的适应性,并在一代或两代中将他们带出人口库.还有其他方法可以处理有效的约束.
# This file is part of DEAP.
#
# DEAP is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as
# published by the Free Software Foundation, either version 3 of
# the License, or (at your option) any later version.
#
# DEAP is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with DEAP. If not, see <http://www.gnu.org/licenses/>.
import random
import numpy as np
from deap import algorithms
from deap import base
from deap import creator
from deap import tools
IND_INIT_SIZE = 5 # Calls to `individual` function
MAX_ITEM = 100 # Max 100 fruit items in basket
NBR_ITEMS = 50 # Start with 50 items in basket
FRUIT_TYPES = 10 # Number of fruit types (apples, bananas, ...)
# Generate a dictionary of random fruit prices.
fruit_price = {i: random.randint(1, 5) for i in range(FRUIT_TYPES)}
# Create fruit items dictionary. The key is item ID, and the
# value is a (weight, price) tuple. Weight is always 1 here.
items = {}
# Create random items and store them in the items' dictionary.
for i in range(NBR_ITEMS):
items[i] = (1, fruit_price[i])
# Create fitness function and an individual (solution candidate)
# A solution candidate in our case is a collection of fruit items.
creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
creator.create("Individual", set, fitness=creator.Fitness)
toolbox = base.Toolbox()
# Randomly initialize the population (a set of candidate solutions)
toolbox.register("attr_item", random.randrange, NBR_ITEMS)
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_item, IND_INIT_SIZE)
def evalBasket(individual):
"""Evaluate the value of the basket and
apply constraints penalty.
"""
value = 0 # Total value of the basket
for item in individual:
value += items[item][1]
# Heavily penalize baskets with 100+ items
if len(individual) > MAX_ITEM:
return 10000, 0
return len(individual), value # (items in basket, value of basket)
def cxSet(ind1, ind2):
"""Apply a crossover operation on input sets.
The first child is the intersection of the two sets,
the second child is the difference of the two sets.
This is one way to evolve new candidate solutions from
existing ones. Think of it as parents mixing their genes
to produce a child.
"""
temp = set(ind1) # Used in order to keep type
ind1 &= ind2 # Intersection (inplace)
ind2 ^= temp # Symmetric Difference (inplace)
return ind1, ind2
def mutSet(individual):
"""Mutation that pops or add an element.
In nature, gene mutations help offspring express new traits
not found in their ancestors. That could be beneficial or
harmful. Survival of the fittest at play here.
"""
if random.random() < 0.5: # 50% chance of mutation
if len(individual) > 0:
individual.remove(random.choice(sorted(tuple(individual))))
else:
individual.add(random.randrange(NBR_ITEMS))
return individual,
# Register evaluation, mating, mutation and selection functions
# so the framework can use them to run the simulation.
toolbox.register("evaluate", evalKnapsack)
toolbox.register("mate", cxSet)
toolbox.register("mutate", mutSet)
toolbox.register("select", tools.selNSGA2)
def main():
random.seed(64)
NGEN = 50
MU = 50
LAMBDA = 100
CXPB = 0.7
MUTPB = 0.2
pop = toolbox.population(n=MU) # Initial population size
hof = tools.ParetoFront() # Using Pareto front to rank fitness
# Keep track of population fitness stats which should
# improve over generations (iterations).
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean, axis=0)
stats.register("std", numpy.std, axis=0)
stats.register("min", numpy.min, axis=0)
stats.register("max", numpy.max, axis=0)
algorithms.eaMuPlusLambda(pop, toolbox, MU,LAMBDA,\
CXPB, MUTPB, NGEN, stats,\
halloffame=hof)
return pop, stats, hof
if __name__ == "__main__":
main()
整数线性规划方法
这自然地建立了一个多步骤的整数计划,其中来自上一步骤的{apples,pears,oranges}的持股量计算了必须约束的持股的相对变化.这里没有最优的概念,但我们可以将"营业额"约束变成一个目标,看看会发生什么.
所提供的解决方案对上图中的解决方案有所改进,并且从篮子持有量的总变化来看,这些解决方案很少.
评论 -
我不知道你是如何计算表格中的"%更改"列的.从第1天到第2天,从20个苹果到21个苹果的变化是4.76%的变化？
在所有的日子里,你在水果中的总持有量正好是100.有一个限制是持有的总和<= 100.没有违规,我只是想确认.
我们可以使用整数优化例程将其设置为整数线性程序ortools.我没有使用过的ILP求解器很长一段时间,而这一次是怎么样的片状我认为(solver.OPTIMAL标志是从来没有如此看来,即使是玩具的问题.此外,ortoolsLP解题未能找到最佳的解决方案如果scipy.linprog工作没有障碍)
h1,d = holdings in apples (number of apples) at end of day d
h2,d = holdings in pears at end of day d
h3,d = holdings in oranges at end of day d
我在这里给出两个建议,一个最小化l1绝对误差的范数,另一个最小化l0常数.
该l1解决方案找到了最小值abs(h1,(d+1) - h1,d)/h1 + ... + abs(h3,(d+1) - h3,d)/h3),希望如果持有量的相对变化之和最小化,则每次持股相对变化的约束低于10%.
唯一阻止它成为线性程序(除整数要求之外)的是非线性目标函数.没问题,我们可以引入松弛变量并使一切变得线性.对于l1配方,引入了6个额外的松弛变量,每个水果2个,以及6个额外的不等式约束.对于l0公式,引入了1个松弛变量,以及6个额外的不等式约束.
这是一个两步过程,例如,替换| apples_new - apples_old |/| apples_old | 使用变量| e |,并添加不等式约束以确保e衡量我们想要的.然后我们替换| e | (e + - e-),每个e +,e-> 0.可以证明e +,e-中的一个将为0,并且(e + + e-)是e的绝对值.这样,对(e +,e-)可以表示正数或负数.标准的东西,但增加了一堆变量和约束.如有必要,我可以更详细地解释一下.
import numpy as np
from ortools.linear_solver import pywraplp
def fruit_basket_l1_ortools():
UPPER_BOUND = 1000
prices = [[2,3,5],
[1,2,4],
[1,2,3]]
holdings = [20,43,37]
values = [348, 251, 213]
for day in range(len(values)):
solver = pywraplp.Solver('ILPSolver',
pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
# solver = pywraplp.Solver('ILPSolver',
# pywraplp.Solver.CLP_LINEAR_PROGRAMMING)
c = ([1,1] * 3) + [0,0,0]
price = prices[day]
value = values[day]
A_eq = [[ 0, 0, 0, 0, 0, 0, price[0], price[1], price[2]]]
b_eq = [value]
A_ub = [[-1*holdings[0], 1*holdings[0], 0, 0, 0, 0, 1.0, 0, 0],
[-1*holdings[0], 1*holdings[0], 0, 0, 0, 0, -1.0, 0, 0],
[ 0, 0, -1*holdings[1], 1*holdings[1], 0, 0, 0, 1.0, 0],
[ 0, 0, -1*holdings[1], 1*holdings[1], 0, 0, 0, -1.0, 0],
[ 0, 0, 0, 0, -1*holdings[2], 1*holdings[2], 0, 0, 1.0],
[ 0, 0, 0, 0, -1*holdings[2], 1*holdings[2], 0, 0, -1.0]]
b_ub = [1*holdings[0], -1*holdings[0], 1*holdings[1], -1*holdings[1], 1*holdings[2], -1*holdings[2]]
num_vars = len(c)
num_ineq_constraints = len(A_ub)
num_eq_constraints = len(A_eq)
data = [[]] * num_vars
data[0] = solver.IntVar( 0, UPPER_BOUND, 'e1_p')
data[1] = solver.IntVar( 0, UPPER_BOUND, 'e1_n')
data[2] = solver.IntVar( 0, UPPER_BOUND, 'e2_p')
data[3] = solver.IntVar( 0, UPPER_BOUND, 'e2_n')
data[4] = solver.IntVar( 0, UPPER_BOUND, 'e3_p')
data[5] = solver.IntVar( 0, UPPER_BOUND, 'e3_n')
data[6] = solver.IntVar( 0, UPPER_BOUND, 'x1')
data[7] = solver.IntVar( 0, UPPER_BOUND, 'x2')
data[8] = solver.IntVar( 0, UPPER_BOUND, 'x3')
constraints = [0] * (len(A_ub) + len(b_eq))
# Inequality constraints
for i in range(0,num_ineq_constraints):
constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_ub[i][j])
# Equality constraints
for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
constraints[i] = solver.Constraint(b_eq[i-num_ineq_constraints], b_eq[i-num_ineq_constraints])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])
# Objective function
objective = solver.Objective()
for i in range(0,num_vars):
objective.SetCoefficient(data[i], c[i])
# Set up as minization problem
objective.SetMinimization()
# Solve it
result_status = solver.Solve()
solution_set = [data[i].solution_value() for i in range(len(data))]
print('DAY: {}'.format(day+1))
print('======')
print('SOLUTION FEASIBLE: {}'.format(solver.FEASIBLE))
print('SOLUTION OPTIMAL: {}'.format(solver.OPTIMAL))
print('VALUE OF BASKET: {}'.format(np.dot(A_eq[0], solution_set)))
print('SOLUTION (apples,pears,oranges): {!r}'.format(solution_set[-3:]))
print('PCT CHANGE (apples,pears,oranges): {!r}\n\n'.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))
# Update holdings for the next day
holdings = solution_set[-3:]
单次运行给出:
DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 348.0
SOLUTION (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [0.0, -4.65, 0.0]
DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 251.0
SOLUTION (apples,pears,oranges): [21.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [5.0, 0.0, 0.0]
DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 213.0
SOLUTION (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [-4.76, 0.0, 0.0]
该l0提法还提出:
def fruit_basket_l0_ortools():
UPPER_BOUND = 1000
prices = [[2,3,5],
[1,2,4],
[1,2,3]]
holdings = [20,43,37]
values = [348, 251, 213]
for day in range(len(values)):
solver = pywraplp.Solver('ILPSolver',
pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
# solver = pywraplp.Solver('ILPSolver',
# pywraplp.Solver.CLP_LINEAR_PROGRAMMING)
c = [1, 0, 0, 0]
price = prices[day]
value = values[day]
A_eq = [[0, price[0], price[1], price[2]]]
b_eq = [value]
A_ub = [[-1*holdings[0], 1.0, 0, 0],
[-1*holdings[0], -1.0, 0, 0],
[-1*holdings[1], 0, 1.0, 0],
[-1*holdings[1], 0, -1.0, 0],
[-1*holdings[2], 0, 0, 1.0],
[-1*holdings[2], 0, 0, -1.0]]
b_ub = [holdings[0], -1*holdings[0], holdings[1], -1*holdings[1], holdings[2], -1*holdings[2]]
num_vars = len(c)
num_ineq_constraints = len(A_ub)
num_eq_constraints = len(A_eq)
data = [[]] * num_vars
data[0] = solver.IntVar(-UPPER_BOUND, UPPER_BOUND, 'e' )
data[1] = solver.IntVar( 0, UPPER_BOUND, 'x1')
data[2] = solver.IntVar( 0, UPPER_BOUND, 'x2')
data[3] = solver.IntVar( 0, UPPER_BOUND, 'x3')
constraints = [0] * (len(A_ub) + len(b_eq))
# Inequality constraints
for i in range(0,num_ineq_constraints):
constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_ub[i][j])
# Equality constraints
for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
constraints[i] = solver.Constraint(int(b_eq[i-num_ineq_constraints]), b_eq[i-num_ineq_constraints])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])
# Objective function
objective = solver.Objective()
for i in range(0,num_vars):
objective.SetCoefficient(data[i], c[i])
# Set up as minization problem
objective.SetMinimization()
# Solve it
result_status = solver.Solve()
solution_set = [data[i].solution_value() for i in range(len(data))]
print('DAY: {}'.format(day+1))
print('======')
print('SOLUTION FEASIBLE: {}'.format(solver.FEASIBLE))
print('SOLUTION OPTIMAL: {}'.format(solver.OPTIMAL))
print('VALUE OF BASKET: {}'.format(np.dot(A_eq[0], solution_set)))
print('SOLUTION (apples,pears,oranges): {!r}'.format(solution_set[-3:]))
print('PCT CHANGE (apples,pears,oranges): {!r}\n\n'.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))
# Update holdings for the next day
holdings = solution_set[-3:]
一次运行就给出了
DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 348.0
SOLUTION (apples,pears,oranges): [33.0, 79.0, 9.0]
PCT CHANGE (apples,pears,oranges): [65.0, 83.72, -75.68]
DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 251.0
SOLUTION (apples,pears,oranges): [49.0, 83.0, 9.0]
PCT CHANGE (apples,pears,oranges): [48.48, 5.06, 0.0]
DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 213.0
SOLUTION (apples,pears,oranges): [51.0, 63.0, 12.0]
PCT CHANGE (apples,pears,oranges): [4.08, -24.1, 33.33]
摘要
该l1配方提供更明智的结果,更低的营业额,更低.然而,最佳性检查在所有运行中失败,这是有关的.我也包括了一个线性求解器,并且无法以某种方式进行可行性检查,我不知道为什么.Google人员为ortools lib提供了宝贵的小文档,其中大部分都是针对C++库的.但是这个l1表述可能是你问题的解决方案,可能会扩展.ILP通常是NP完全的,最有可能的是你的问题.
另外 - 第2天是否存在解决方案？你如何定义%变化,以便它在上面的图表中？如果我知道我可以重新改变上面的不平等,我们将得到一般的解决方案.
这不是一个答案,而是试图让一个关于"%变化"可能意味着什么的信息(向后计算的每个项目的计数变化总和)更容易被像素堆中的非信徒所接受:
| Day 1 ! Day 2 change ! Day 3 change ! Day 4 change
|$/1| # | $ !$/1| # | % | $ !$/1| # | % | $ !$/1| # | % | $
Apples | 1 | 20 | 20 ! 2 | 21 | 4.76 | 42 ! 1 | 21 | 0 | 21 ! 1 | 22 | 4.55 | 22
Pears | 2 | 43 | 86 ! 3 | 42 | 2.38 | 126 ! 2 | 43 | 2.33 | 86 ! 2 | 43 | 0 | 86
Oranges| 3 | 37 | 111 ! 5 | 36 | 2.78 | 180 ! 4 | 36 | 0 | 144 ! 3 | 35 | 2.86 | 105
Total | 100 | 217 ! 100 | 9.92 | 348 ! 100 | 2.33 | 251 ! 100 | 7.40 | 213
| 归档时间： |
|
| 查看次数： |
1407 次 |
| 最近记录： |