Select 同一个物品在背包问题中多次出现[纸浆]
Select the same item several times in the knapsack problem [pulp]
我正在上课'discrete optimization course
其中,在课程中使用了一个名为 Minizinc 的工具来解决问题。
我想将 class 个示例翻译成 python,从这个开始:
我正在使用此示例代码重现结果:
v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))
# Create model
m = LpProblem("Knapsack", LpMaximize)
# Variables
x = LpVariable.dicts('x', items, lowBound=0, upBound=1, cat=LpInteger)
# Objective
m += sum(v[i]*x[i] for i in items)
# Constraint
m += sum(w[i]*x[i] for i in items) <= limit
# Optimize
m.solve()
# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])
# Print the value of the variables at the optimum
for i in items:
print("%s = %f" % (x[i].name, x[i].varValue))
# Print the value of the objective
print("Objective = %f" % value(m.objective))
但这是一个错误的答案,因为只采用了一种。
如何将每个项目 (dict q) 的可用数量添加到约束中?
您需要对代码进行两处非常小的更改。首先,您需要删除在 x
变量上设置的上限。目前你有二进制变量 x[i]
,它只能是一或零。
其次,您需要添加有效地为每个项目设置自定义上限的约束。下面的工作代码和结果解决方案 - 如您所见,选择了多个扳手(最高 v/w
比率),用一个锤子填满剩余的少量 space。
from pulp import *
v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))
# Create model
m = LpProblem("Knapsack", LpMaximize)
# Variables
x = LpVariable.dicts('x', items, lowBound=0, cat=LpInteger)
# Objective
m += sum(v[i]*x[i] for i in items)
# Constraint
m += sum(w[i]*x[i] for i in items) <= limit
# Quantity of each constraint:
for i in items:
m += x[i] <= q[i]
# Optimize
m.solve()
# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])
# Print the value of the variables at the optimum
for i in items:
print("%s = %f" % (x[i].name, x[i].varValue))
# Print the value of the objective
print("Objective = %f" % value(m.objective))
print("Total weight = %f" % sum([x[i].varValue*w[i] for i in items]))
哪个returns:
状态 = 最佳
x_hammer = 1.000000
x_screwdriver = 0.000000
x_towel = 0.000000
x_wrench = 47.000000
Objective = 476.000000
Total weight = 1000.000000
我正在上课'discrete optimization course 其中,在课程中使用了一个名为 Minizinc 的工具来解决问题。
我想将 class 个示例翻译成 python,从这个开始:
v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))
# Create model
m = LpProblem("Knapsack", LpMaximize)
# Variables
x = LpVariable.dicts('x', items, lowBound=0, upBound=1, cat=LpInteger)
# Objective
m += sum(v[i]*x[i] for i in items)
# Constraint
m += sum(w[i]*x[i] for i in items) <= limit
# Optimize
m.solve()
# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])
# Print the value of the variables at the optimum
for i in items:
print("%s = %f" % (x[i].name, x[i].varValue))
# Print the value of the objective
print("Objective = %f" % value(m.objective))
但这是一个错误的答案,因为只采用了一种。 如何将每个项目 (dict q) 的可用数量添加到约束中?
您需要对代码进行两处非常小的更改。首先,您需要删除在 x
变量上设置的上限。目前你有二进制变量 x[i]
,它只能是一或零。
其次,您需要添加有效地为每个项目设置自定义上限的约束。下面的工作代码和结果解决方案 - 如您所见,选择了多个扳手(最高 v/w
比率),用一个锤子填满剩余的少量 space。
from pulp import *
v = {'hammer':6, 'wrench':10, 'screwdriver':8, 'towel':40}
w = {'hammer':13, 'wrench':21, 'screwdriver':17, 'towel':100}
q = {'hammer':1000, 'wrench':400, 'screwdriver':500, 'towel':150}
limit = 1000
items = list(sorted(v.keys()))
# Create model
m = LpProblem("Knapsack", LpMaximize)
# Variables
x = LpVariable.dicts('x', items, lowBound=0, cat=LpInteger)
# Objective
m += sum(v[i]*x[i] for i in items)
# Constraint
m += sum(w[i]*x[i] for i in items) <= limit
# Quantity of each constraint:
for i in items:
m += x[i] <= q[i]
# Optimize
m.solve()
# Print the status of the solved LP
print("Status = %s" % LpStatus[m.status])
# Print the value of the variables at the optimum
for i in items:
print("%s = %f" % (x[i].name, x[i].varValue))
# Print the value of the objective
print("Objective = %f" % value(m.objective))
print("Total weight = %f" % sum([x[i].varValue*w[i] for i in items]))
哪个returns:
状态 = 最佳
x_hammer = 1.000000
x_screwdriver = 0.000000
x_towel = 0.000000
x_wrench = 47.000000
Objective = 476.000000
Total weight = 1000.000000