PuLP의 배낭, 선택된 항목 수에 대한 제약 조건 추가

Question

나는 내 배낭 문제를 해결하는 puLP 코드가 있습니다.

prob = LpProblem("Knapsack problem", LpMaximize) 

x1 = LpVariable("x1", 0, 12, 'Integer') 
x2 = LpVariable("x2", 0, 12, 'Integer') 
x3 = LpVariable("x3", 0, 12, 'Integer') 
x4 = LpVariable("x4", 0, 12, 'Integer') 
x5 = LpVariable("x5", 0, 12, 'Integer') 
x6 = LpVariable("x6", 0, 12, 'Integer') 
x7 = LpVariable("x7", 0, 12, 'Integer') 
x8 = LpVariable("x8", 0, 12, 'Integer') 
x9 = LpVariable("x9", 0, 12, 'Integer') 
x10 = LpVariable("x10", 0, 12, 'Integer') 
x11 = LpVariable("x11", 0, 12, 'Integer') 
x12 = LpVariable("x12", 0, 12, 'Integer') 
x13 = LpVariable("x13", 0, 12, 'Integer') 
x14 = LpVariable("x14", 0, 12, 'Integer') 
x15 = LpVariable("x15", 0, 12, 'Integer') 
x16 = LpVariable("x16", 0, 12, 'Integer') 
x17 = LpVariable("x17", 0, 12, 'Integer') 
x18 = LpVariable("x18", 0, 12, 'Integer') 
x19 = LpVariable("x19", 0, 12, 'Integer') 
x20 = LpVariable("x20", 0, 12, 'Integer') 
x21 = LpVariable("x21", 0, 12, 'Integer') 
x22 = LpVariable("x22", 0, 12, 'Integer') 
x23 = LpVariable("x23", 0, 12, 'Integer') 
x24 = LpVariable("x24", 0, 12, 'Integer') 
x25 = LpVariable("x25", 0, 12, 'Integer') 

prob += 15 * x1 + 18 * x2 + 18 * x3 + 23 * x4 + 18 * x5 + 20 * x6 + 15 * x7 + 16 * x8 + 12 * x9 + 12 * x10 + 25 * x11 + 25 * x12 + 28 * x13 + 35 * x14 + 28 * x15 + 28 * x16 + 25 * x17 + 25 * x18 + 25 * x19 + 28 * x20 + 25 * x21 + 32 * x22 + 32 * x23 + 28 * x24 + 25 * x25, "obj" 

prob += 150 * x1 + 180 * x2 + 180 * x3 + 230 * x4 + 180 * x5 + 200 * x6 + 150 * x7 + 160 * x8 + 120 * x9 + 120 * x10 + 250 * x11 + 250 * x12 + 280 * x13 + 350 * x14 + 280 * x15 + 280 * x16 + 250 * x17 + 250 * x18 + 250 * x19 + 280 * x20 + 250 * x21 + 320 * x22 + 320 * x23 + 280 * x24 + 250 * x25 == 6600, "c1" 

prob.solve() 

print "Status:", LpStatus[prob.status] 

for v in prob.variables(): 
    print v.name, "=", v.varValue 

print ("objective = %s" % value(prob.objective)) 

하지만 다른 조건을 추가 할 필요가이 코드에

예를 들어, 비 - 제로 prob.variables의 수는 (말)이 10

누군가가 도움을 수 제한을 동일해야?

UPDATE

: 나는 어떻게 보장 것이다

Status: Optimal 
X1 = 1.0 
x10 = 0.0 
x11 = 0.0 
x12 = 0.0 
x13 = 0.0 
x14 = 0.0 
x15 = 0.0 
x16 = 0.0 
x17 = 0.0 
x18 = 0.0 
x19 = 0.0 
x2 = 0.0 
x20 = 0.0 
x21 = 0.0 
x22 = 0.0 
x23 = 0.0 
x24 = 0.0 
x25 = 0.0 
x3 = 0.0 
x4 = 11.0 
x5 = 0.0 
x6 = 10.0 
x7 = 0.0 
x8 = 12.0 
x9 = 0.0 
objective = 660.0 

이 아닌 0 값이 prob.variables의 수는 4와 동일

하지만 10 필요하다고 :이 코드에 대한

나는 출력이 있나요?

Answer 1

0이 아닌 값을 원하는 경우 새 0/1 변수를 도입하여이를 수행 할 수 있습니다. 제제

모든 이진 {0,1}

X [내가]> 0, 우리는 Y 원한다면 [I]를한다 (25 개) 새로운 Y 변수 [y1..y25] 소개 값 1을 사용하십시오. 다음 제한 조건을 추가하여 수행 할 수 있습니다. 지금

x[i] < y[i] x M (where M is some big number, say 10,000) for 1 in 1..25 

적어도 10 Y 값은 비제로되도록, 우리는 Y 위에 1

합하도록 적어도 10하려는 [1] ... Y [25] > = 10으로 보장합니다.

있음 PuLP puLP 코드는 테스트되지 않았지만 진행 방법을 알려줍니다.

x=[] 
y=[] 

for index in range(25): 
    y[index] = LpVariable("y"+str(index), 0, 1) #binary variables 
    prob += x[index] <= 10000 * y[index], "If x%s is non-zero, then y%s is forced to be 1",%index, %index 

prob += lpSum([y[i] for i in range(25)]) >= 10,"Ensuring at least 10 items are non-zero" 

희망이 있습니다.

Answer 2

내가 두 번째 제공된 대답뿐만 아니라 짧은 코드 펄프의 (그리고 파이썬의) 지능형리스트를보다 효율적으로 사용하기에 대해 언급합니다 : 내가 거기에 약간의 계수를 잘못 입력했을 수 있지만, 난

from pulp import * 
prob = LpProblem("Knapsack problem", LpMaximize) 
cost = [15,18,18,23,18,20,15,16,12,12,25,25,28,35,28,28,25,25,25,28,25,32,32,28,25] 
x = LpVariable.dicts('x',range(1,26),lowBound=0,upBound=12,cat=pulp.LpInteger) 
cap = [150,180,180,230,180,200,150,160,120,120,250,250,280,350,280,280,250,250,250,280,250,320,320,280,250] 
prob += pulp.lpSum([cost[ix]*x[ix] for ix in range(1,25)]), "obj" 
prob += pulp.lpSum([cap[ix]*x[ix] for ix in range(1,25)]) == 6600, "c1" 
prob.solve() 

print "Status:", LpStatus[prob.status] 

for v in prob.variables(): 
    if v.varValue>0.0001: 
     print v.name, "=", v.varValue 

print ("objective = %s" % value(prob.objective)) 

당신은 내 요점을 얻었을거야.