Problema

Estoy trabajando en un problema de Python, donde un concesionario de automóviles quiere acumular una lista de vehículos donde el kilometraje total en los vehículos elegidos es máximo (restricción 1, no sé por qué querría el mayor kilometraje, pero es lo que lo es) y tiene que permanecer por debajo de cierto presupuesto (restricción 2, $ 300000).

Pregunta

Sé cómo ordenar los datos en función de 1 condición, pero ordenarlos en función de 2 valores es más complicado de lo que pensaba. ¿Cuál es la mejor manera de resolver mi problema? Por favor vea mi intento a continuación.

Pequeña muestra de datos

--------------------------------------------------
| Licence | Manufacturer | Price         | Mileage
--------------------------------------------------
|   1     | Audi         |     42000     | 8000
--------------------------------------------------
|   2     | Mercedes     |     33000     | 15000
--------------------------------------------------
|   3     | Lexus        |     38000     | 10000
--------------------------------------------------
|   4     | BMW          |     25000     | 20000
--------------------------------------------------
|   5     | Mercedes     |     55000     | 33000
--------------------------------------------------

Mi intento

Primero pensé en asignar una especie de peso entre el kilometraje y el precio, porque un automóvil podría tener un alto kilometraje, pero su precio también podría ser muy alto, así que pensé que la clasificación basada solo en el kilometraje es incorrecta. Por ejemplo, supongamos que tengo tres automóviles, A, B y C. El automóvil A tiene 10000 millas y cuesta $ 20000. El auto B tiene 20000 millas pero cuesta $ 40000. En este caso, elegir cualquiera de ellos no haría la diferencia. Pero suponga que el automóvil C tiene 25000 millas, pero cuesta $ 80000. El algoritmo primero debe considerar los autos A y B antes de considerar C, a pesar de que C tiene el mayor kilometraje, no vale la pena el precio.

Así que creé una nueva columna que es la relación entre el kilometraje y el precio y ordené esta lista usando esa relación como la clave y luego la invirtí para obtener las relaciones comenzando desde el valor más alto. Luego recorrí esta lista, agregando los autos a una nueva lista si el monto total no excedía el presupuesto.

cost = 0;

with open(fileName, 'r') as inputFile:
    list1 = csv.reader(inputFile, delimiter=' ')
    list2 = [(row[0], row[1], row[2], row[3],  float(row[3])/float(row[2])) for l in list1]
    list2.sort(key = lambda x: x[4])
    list2.reverse()


cars2Buy = []
for l in list2:
    if (cost + int(row[2])) <= 300000:
       cost += int(row[2])
       cars2Buy.append((row[0], row[1], row[2], row[3]))

    else: break

Sin embargo, también probé un conjunto de datos diferente y ordené según el kilometraje, por ejemplo:

 list2.sort(key = lambda x: x[3]), 

En lugar de

list2.sort(key = lambda x: x[4])

Y, sorprendentemente, en ese conjunto de datos en particular, la clasificación basada solo en el kilometraje me dio una lista de automóviles que tenían más kilometraje que mi algoritmo de 'ponderación' y todavía estaban por debajo del presupuesto. Esto debe significar que mi forma de resolver este problema es defectuosa, pero no puedo ver por qué. ¡Apreciaria cualquier sugerencia! Gracias.

0
user3451660 9 sep. 2018 a las 14:20

3 respuestas

La mejor respuesta

Estoy de acuerdo con Petro, esto parece ser un problema de mochila 0/1, con N = número de automóviles y W = precio máximo de 300000 (y valor = kilometraje del automóvil).

Y sí, la mochila es NP-Hard, por lo que no tiene un algoritmo polinomial. Sin embargo, hay un algoritmo bastante rápido que se ejecuta en O (NW), que es bueno para algunos miles de automóviles en nuestro caso.

Podemos adaptar el algoritmo de mochila 0/1 desde la página de wikipedia para que use memoria 2N en su lugar de NO para ahorrar tiempo asignando memoria. En cuanto a cómo funciona el algoritmo de mochila:

  • m[i][j] es el kilometraje máximo de los primeros i automóviles con el precio total como máximo j.
  • dado que, en cada selección de automóviles, el automóvil ith está en la selección o no, podemos calcular m[i][j] considerando el mejor valor de dos casos:
    1. el coche ith está en la selección óptima. El valor óptimo para esto es la selección de automóviles i-1 con un precio total como máximo j-cost[i] (es decir, m[i-1][j-cost[i]]
    2. el coche ith no está en la selección óptima. El valor óptimo es el mejor valor para seleccionar i-1 automóviles con precio como máximo j (es decir, m[i-1][j])

Código:

#!/usr/bin/env python
import csv

def solve():
    fileName = 'hi.in'
    with open(fileName, 'r') as inputFile:
        list1 = csv.reader(inputFile, delimiter=',')
        list2 = [(int(row[0]), row[1], int(row[2]), int(row[3])) for row in list1]

    cars2Buy = get_cars(list2)
    print(cars2Buy)


def get_cars(l):
    N = len(l)
    W = 300000
    l = [0]+l # make list one-based

    # 2N array
    m = [[0 for _ in range(W+1)] for _ in range(2)]

    w = 2 # weight is the price
    v = 3 # value is the mileage
    cars2Buy = []

    for i in range(1, N+1):
        # space-optimisation, move one to zero
        for j in range(0, W+1):
            m[0][j] = m[1][j]

        for j in range(0, W+1):
            if j-l[i][w] < 0:
                m[1][j] = m[0][j]
            else:
                m[1][j] = max(m[0][j], m[0][j-l[i][w]] + l[i][v])

        # if the optimal value for [1,i] is larger than [1,i-1],
        # then the car must be in the selection
        if m[1][W] > m[0][W]:
            cars2Buy.append(l[i])

    return cars2Buy

def main():
    solve()

main()
1
D Slee 10 sep. 2018 a las 01:54

Pruebe esto con pandas, sería mucho más fácil, vea el siguiente ejemplo:

import pandas as pd

df = pd.read_csv("filename.csv", lineterminator='\r')  #read csv file into dataframe

df.sort_values('Mileage', ascending=False, inplace=True)  #sort Mileage column greater to smaller

df = df.loc[df['Price'] > 350000]   #filter price column based on condition

print(df)    #print the dataframe

print(df['Manufacturer'])    #you can print a specific column
0
Chandila07 9 sep. 2018 a las 13:47

El problema que está describiendo me parece que es un caso problema de mochila: ha configurado artículos (lista de automóviles), cada uno con un valor (kilometraje) y un peso (precio) y una mochila (selección de automóviles) con una capacidad limitada en términos de peso (presupuesto total). Desea tener una selección de automóviles que maximice el valor de los automóviles, manteniendo el peso total por debajo de la capacidad.

Debe saber que este es un problema difícil (NP-hard) y depende de tamaño de sus datos, puede llevar demasiado tiempo encontrar la solución óptima. Por lo tanto, a menudo tiene que recurrir a una solución aproximada.

El algoritmo que está describiendo (ordenando por relación valor / peso y seleccionando los elementos principales hasta que la mochila esté llena) es el algoritmo codicioso que proporciona una solución aproximada que no se garantiza que sea óptima. Por lo tanto, supongo que en su caso el algoritmo codicioso no está encontrando la solución óptima (mientras que se puede encontrar una mejor solución seleccionando los elementos principales por valor).

Un caso simple en el que esto sucede es el siguiente: suponga que tiene un presupuesto de 10K y una lista de 2 autos. Uno tiene un kilometraje de 9K y un precio de 10K, el otro con un kilometraje y un precio igual a 2K. El segundo automóvil tiene una mejor relación milla / precio (1 en lugar de 0,9), pero si solo selecciona el automóvil con más kilometraje, tiene una mejor solución (en este caso, claramente es la solución óptima).

Actualizar

Para encontrar implementaciones que le brinden la solución óptima, debe buscar en Google "knapsack solver python" o algo similar. Debería encontrar cosas como this (usando las herramientas OR de Google) o eso (usando PuLP u otras bibliotecas).

3
pietroppeter 9 sep. 2018 a las 14:34