在背包问题中多次选择相同的项目[纸浆]

Question

我正在做一个名为'discrete optimization course的课程，在这个过程中，一个名为Minizinc的工具用于解决问题。

我想将类示例转换为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）的可用金额添加到约束中？

Answer 1

您需要对代码进行两次非常小的更改。首先，您需要删除在x变量上设置的上限。在你有二进制变量x[i]的时刻，它只能是一个或零。

其次，您需要添加约束，这些约束有效地为每个项设置自定义上限。下面的工作代码和最终解决方案 - 你可以看到多个扳手（最高的v/w比率）被选中，用一把锤子填满剩下的少量空间。

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]))

哪个回报：

状态=最佳

x_hammer = 1.000000
x_screwdriver = 0.000000
x_towel = 0.000000
x_wrench = 47.000000
Objective = 476.000000
Total weight = 1000.000000