aW1wb3J0IHB1bHAgCgojIERhdG9zIGRlbCBwcm9ibGVtYQpOID0gMTAgICMgbiZ1YWN1dGU7bWVybyBkZSBvYmpldG9zCk0gPSAzICAgIyBuJnVhY3V0ZTttZXJvIGRlIG1vY2hpbGFzClAgPSBbNjgsIDMzLCA0NSwgMzUsIDI2LCA0NywgNDEsIDU5LCA1MywgMjRdICAjIHBlc29zIGRlIGxvcyBvYmpldG9zClYgPSBbNDAsIDM0LCA0NywgNDUsIDIyLCAyNiwgNDQsIDIyLCA0MCwgMjBdICAjIHZhbG9yZXMgZGUgbG9zIG9iamV0b3MKSyA9IFsxMjgsIDExOCwgMTIxXSAgIyBjYXBhY2lkYWRlcyBkZSBsYXMgbW9jaGlsYXMKIAojIENyZWFyIGVsIHByb2JsZW1hIGRlIG1heGltaXphY2kmb2FjdXRlO24KcHJvYmxlbSA9IExwUHJvYmxlbSgmcXVvdDtNdWx0aS1LbmFwc2Fjay1Qcm9ibGVtJnF1b3Q7LCBMcE1heGltaXplKQogCiMgVmFyaWFibGVzIGRlIGRlY2lzaSZvYWN1dGU7bjogeFtpXVtqXSBpbmRpY2Egc2kgZWwgb2JqZXRvIGkgZXN0JmFhY3V0ZTsgZW4gbGEgbW9jaGlsYSBqCnggPSBbW0xwVmFyaWFibGUoZiZxdW90O3hfe2l9X3tqfSZxdW90OywgY2F0PSZxdW90O0JpbmFyeSZxdW90OykgZm9yIGogaW4gcmFuZ2UoTSldIGZvciBpIGluIHJhbmdlKE4pXQogCiMgRnVuY2kmb2FjdXRlO24gb2JqZXRpdm86IG1heGltaXphciBlbCB2YWxvciB0b3RhbApwcm9ibGVtICs9IGxwU3VtKFZbaV0gKiB4W2ldW2pdIGZvciBpIGluIHJhbmdlKE4pIGZvciBqIGluIHJhbmdlKE0pKQogCiMgUmVzdHJpY2Npb25lcyBkZSBjYXBhY2lkYWQgcGFyYSBjYWRhIG1vY2hpbGEKZm9yIGogaW4gcmFuZ2UoTSk6CiAgICBwcm9ibGVtICs9IGxwU3VtKFBbaV0gKiB4W2ldW2pdIGZvciBpIGluIHJhbmdlKE4pKSAmbHQ7PSBLW2pdLCBmJnF1b3Q7Q2FwYWNpZGFkX21vY2hpbGFfe2p9JnF1b3Q7CiAKIyBSZXN0cmljY2kmb2FjdXRlO24gZGUgdW5pY2lkYWQ6IGNhZGEgb2JqZXRvIGRlYmUgZXN0YXIgZW4gdW5hICZ1YWN1dGU7bmljYSBtb2NoaWxhCmZvciBpIGluIHJhbmdlKE4pOgogICAgcHJvYmxlbSArPSBscFN1bSh4W2ldW2pdIGZvciBqIGluIHJhbmdlKE0pKSAmbHQ7PSAxLCBmJnF1b3Q7VW5pY2lkYWRfb2JqZXRvX3tpfSZxdW90OwogCiMgUmVzb2x2ZXIgZWwgcHJvYmxlbWEKcHJvYmxlbS5zb2x2ZSgpCiAKIyBJbXByaW1pciBlbCB2YWxvciAmb2FjdXRlO3B0aW1vIGRlIGxhIGZ1bmNpJm9hY3V0ZTtuIG9iamV0aXZvCnZhbG9yX29wdGltbyA9IHByb2JsZW0ub2JqZWN0aXZlLnZhbHVlKCkKcHJpbnQoZiZxdW90O1ZhbG9yICZvYWN1dGU7cHRpbW8gZGUgbGEgZnVuY2kmb2FjdXRlO24gb2JqZXRpdm86IHt2YWxvcl9vcHRpbW99ICZldXJvOyZxdW90OykKIAojIEltcHJpbWlyIGxhIGFzaWduYWNpJm9hY3V0ZTtuICZvYWN1dGU7cHRpbWEgZGUgbG9zIG9iamV0b3MKZm9yIGkgaW4gcmFuZ2UoTik6CiAgICBmb3IgaiBpbiByYW5nZShNKToKICAgICAgICBpZiB4W2ldW2pdLnZhbHVlKCkgPT0gMToKICAgICAgICAgICAgcHJpbnQoZiZxdW90O09iamV0byB7aSsxfSBhc2lnbmFkbyBhIGxhIG1vY2hpbGEge2orMX0mcXVvdDsp

import pulp 

# Datos del problema
N = 10  # número de objetos
M = 3   # número de mochilas
P = [68, 33, 45, 35, 26, 47, 41, 59, 53, 24]  # pesos de los objetos
V = [40, 34, 47, 45, 22, 26, 44, 22, 40, 20]  # valores de los objetos
K = [128, 118, 121]  # capacidades de las mochilas
 
# Crear el problema de maximización
problem = LpProblem("Multi-Knapsack-Problem", LpMaximize)
 
# Variables de decisión: x[i][j] indica si el objeto i está en la mochila j
x = [[LpVariable(f"x_{i}_{j}", cat="Binary") for j in range(M)] for i in range(N)]
 
# Función objetivo: maximizar el valor total
problem += lpSum(V[i] * x[i][j] for i in range(N) for j in range(M))
 
# Restricciones de capacidad para cada mochila
for j in range(M):
    problem += lpSum(P[i] * x[i][j] for i in range(N)) <= K[j], f"Capacidad_mochila_{j}"
 
# Restricción de unicidad: cada objeto debe estar en una única mochila
for i in range(N):
    problem += lpSum(x[i][j] for j in range(M)) <= 1, f"Unicidad_objeto_{i}"
 
# Resolver el problema
problem.solve()
 
# Imprimir el valor óptimo de la función objetivo
valor_optimo = problem.objective.value()
print(f"Valor óptimo de la función objetivo: {valor_optimo} €")
 
# Imprimir la asignación óptima de los objetos
for i in range(N):
    for j in range(M):
        if x[i][j].value() == 1:
            print(f"Objeto {i+1} asignado a la mochila {j+1}")