Home / Questions / 4877
Accepted
Eduardo Munizaga
Asked: 2020-02-27 19:44:53 +0800 CST 2020-02-27 19:44:53 +0800 CST

背包问题

  • 772

我正在处理一个客户案例，他申请使用背包问题算法。我正在使用附加的代码，它或多或少地工作并且有错误。

该示例有 12 个不同重量的包裹（总重 1260 公斤）以及相关的价值或价格。目标是装载最大数量的包裹，在不超过卡车最大负载的情况下优先考虑最高值。

例如;

1.- 如果卡车的最大负载为 9 公斤，此代码应该选择Paquete 2 Peso :9 valor :160而不是Paquete 2 Peso :9 valor :150（但它没有，它选择零）。

2.- 另一方面，如果卡车的最大负载为 500 公斤，请选择以下选项：

Paquete 9 Peso :230 valor :591
Paquete 3 Peso :153 valor :200
Paquete 4 Peso :50 valor :160
Paquete 2 Peso :9 valor :160
Paquete 1 Peso :9 valor :150

Peso total paquetes: 451
Valor total paquetes: 1261

做这项工作但不是很好（完成 493 收费将缺少 7 和 5）

3.- 如果卡车的最大负载为 230，请选择以下选项：

Paquete 9 Peso :9 valor :230

如果它完成了这项工作但效果不佳，因为最好的选择如下：

Paquetes 1, 2, 4 y 5
Con un peso peso total de 83
y un valor valor total de 530

因为效率更高。

代码：

from itertools import takewhile

#Paquetes: "Nombre del paquete", Kilos, Precio
PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 9, 160), ("Paquete 3", 153, 200), ("Paquete 4", 50, 160),
    ("Paquete 5", 15, 60), ("Paquete 6", 66, 45), ("Paquete 7", 27, 60), ("Paquete 8", 39, 40),
    ("Paquete 9", 230, 591), ("Paquete 10", 520, 10), ("Paquete 11", 110, 70), ("Paquete 12", 32, 30))

def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)

def proceso_peso(item):
    nombre, peso, valor = item
    proceso_peso.peso_maximo -= peso
    return proceso_peso.peso_maximo >= 0    

#carga máxima del camión
proceso_peso.peso_maximo = 750


carga_lista = list(takewhile(proceso_peso, reversed(sorted(PAQUETES, key=proceso_valor))))

sumacarga = 0
sumavalor = 0

for item in carga_lista:
    print item[0] + ' Peso :%i' % item[1] + ' valor :%i' % item[2]
    sumacarga = sumacarga + item[1]
    sumavalor = sumavalor + item[2]

print ''
print 'Peso total paquetes: %i' % sumacarga
print 'Valor total paquetes: %i' % sumavalor

有一些我看不到的东西，我需要帮助，问题是：是什么让我的代码无法在较小的最大负载值（例如 9 或 100）下工作？这里缺少什么数学运算来改善结果？

python

2 Answers

  1. Best Answer

    这比看起来简单：您缺少的是价格/重量关系，因为您所做的是 process_value 函数仅从方程式中返回一个数据您将重量留在哪里？如果您想要的是最大数量的包裹，优先考虑价值最高的包裹，您必须将价格除以价值，以便排序返回相关键。我不知道我是否在解释自己，但你必须做的是：

    def proceso_valor(item):
    nombre, peso, valor = item
    return float(valor)/ float(peso)

    并准备好，这样排序将为您提供 4 个元素，其中第四个元素将是您正在寻找的关系。如果您尝试使用 process_weight.weight_maximum = 500，它会为您提供等于 493 而不是 451 的负载，就像您对两个丢失的包所说的那样。

    • 12

  2. 背包问题是一个 NP 问题，也就是说，你不会找到一个总能获得最优解的算法。但是，您可以做的是丢弃表现最差的情况以保留最佳解决方案。

    也就是说，您的算法应该有两个目标：

    1. 放数量最多的包裹
    2. 在获得的解决方案中，保留那些增加最大价值的解决方案

    在您的方法中，不清楚按价值优先排序是将最昂贵的包裹放在首位还是总金额最高。我猜是后一种情况。虽然问题也可以反过来说：想要承载最昂贵的负载，但又不超过卡车的负载限制。

    好吧，您的算法首先按值排序，然后保留适合最大负载的那些。嗯！这与您应该尝试的相反。首先，从最大负载中减去所有昂贵的包。例如，尝试两个包：

    proceso_peso.peso_maximo = 750

PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 1000, 10000)
    )

carga_lista = list(takewhile(proceso_peso, reversed(sorted(PAQUETES, key=proceso_valor))))

    包2有很多价值和很多重量。检查 withproceso_peso减去它的权重proceso_peso.peso_maximo，这是负数，并takewhile最终返回一个空列表。

    看到这个错误后，我的建议是不要使用函数属性，更重要的是，不要在迭代中更改问题条件（如果这样做，请使其看起来清晰）。对于前者，使用面向对象编程；对于后者，使用函数式编程。对于两者，请使用 python。

    背包问题得到了很好的研究。当然，您会发现几种算法或多或少地试图快速找到解决方案。如果它对您有所帮助，我将向您展示如何通过“蛮力”完成它，尽管在某些情况下需要很长时间：

    from operator import itemgetter

#Paquetes: "Nombre del paquete", Kilos, Precio
PAQUETES = (
    ("Paquete 1", 9, 150), ("Paquete 2", 9, 160), ("Paquete 3", 153, 200), ("Paquete 4", 50, 160),
    ("Paquete 5", 15, 60), ("Paquete 6", 66, 45), ("Paquete 7", 27, 60), ("Paquete 8", 39, 40),
    ("Paquete 9", 230, 591), ("Paquete 10", 520, 10), ("Paquete 11", 110, 70), ("Paquete 12", 32, 30))

#carga máxima del camión
PESOMAXIMO = 230

# Útiles para acceso al peso y valores (irían mejor definiendo una clase)
get_peso = itemgetter(1)
get_valor = itemgetter(2)

def total_peso(paquetes):
    return sum(get_peso(x) for x in paquetes)

def total_valor(paquetes):
    return sum(get_valor(x) for x in paquetes)

# Obtención de todas las combinaciones posibles
# Función recursiva
def combinaciones(paquetes, peso_maximo):
    paqs = [ p for p in paquetes if get_peso(p) <= peso_maximo ]
    resultado = []
    for p in paqs:
        res = combinaciones([x for x in paqs if x!=p], peso_maximo - get_peso(p))
        if len(res) == 0:
            resultado.append([p])
        else:
            resultado.extend([[p]+x for x in res])
    return resultado

# solución
max(combinaciones(PAQUETES, PESOMAXIMO), key=total_valor)
    • 2