Corrispondenza di 2 serie di articoli per prezzo

Question

Corrispondenza di 2 serie di articoli per prezzo

Naviga le tue risposte

#1 da (1 voti)
#2 da (0 voti)

2

Sto cercando di risolvere il seguente problema nel modo più efficiente che riesco a trovare.

Voglio scambiare i miei articoli con articoli di qualcun'altro, ogni articolo ha un prezzo e un valore.

Voglio massimizzare il valore degli articoli che scambiamo, quindi ad esempio:

I miei articoli:

Banana, P: 10, V: 5  
Pen, P:3, V:1  
Paper, P: 1, V: 1

Loro articoli:

Phone, P: 10, V: 8  
Key, P: 1, V: 2  
Wallet, P: 30, V: 100

Puoi vedere che posso scambiare Banana e Carta (con valore 6) con Telefono e Chiave (con valore 10)

Posso pagare più del dovuto ma non posso pagare di meno e l'importo da pagare in eccesso è perso. Attualmente la mia soluzione è quella di utilizzare generare tutte le possibili combinazioni dei miei articoli e cercare di abbinare il prezzo all'algoritmo dello zaino e controllare ogni risultato.

Questo però non è molto efficiente perché posso avere più di 1000 oggetti (sia il mio che l'altra persona).

Qualcuno ha una possibile soluzione a questo problema? Ho bisogno che sia efficiente ma che mi dia anche la soluzione migliore (valore migliore)

Gli elementi non sono infiniti e hanno un limite.
Non ho una scala quanto sia efficiente avere bisogno ne ho bisogno per uno scenario di vita reale in cui utilizzo un processore i7 6700 a 4 core e il problema si esegue per centinaia di volte con diversi set.
Posso pagare più del dovuto, tuttavia, il valore è correlato al prezzo. e così Se scambi articoli del valore di 100 per 10 (prezzi) ne ho persi 90 (puoi pensare ai dollari se aiuta) e quindi solo per rompere il valore di cui ho bisogno per guadagnare oltre il +90.
Decido i valori di ogni elemento dal mio database

performance algorithms node.js

posta RythemOfTheDay 05.10.2017 - 21:24

fonte

2 risposte

Leggi altre domande sui tag performance algorithms node.js

HA per due zone di disponibilità in AWS Come posso creare i dati del test front-end in base allo schema del modello di back-end?

score 1 · Answer 1

Come punto di partenza ...

Ordina i loro articoli per valore diviso per costo, in ordine decrescente. Questo ti dà un elenco dei loro articoli con gli oggetti più preziosi in alto. Seleziona gli elementi dalla cima di questo elenco fino a quando la somma del costo degli articoli selezionati incontra un costo fisso. Evita di selezionare articoli senza valore (v = 0).

Quindi ordina i tuoi articoli per valore diviso per costo, in ordine crescente. Questo ti dà un elenco dei tuoi articoli con gli oggetti meno preziosi in alto. Seleziona elementi dalla cima di questo elenco fino a quando la somma del costo degli articoli selezionati soddisfa lo stesso costo fisso.

Se il rapporto valore / costo complessivo dei loro articoli supera il rapporto valore / costo complessivo dei tuoi articoli (dopo aver aggiustato per qualsiasi differenza di prezzo tra i due elenchi selezionati), puoi scambiare gli articoli selezionati per gli articoli selezionati.

score 0 · Answer 2

Sulla base dei tuoi commenti, ti suggerisco il seguente approccio:

//Define your data structure
typedef struct {
  int price;
  int value;
} Item;

//Sorts by price, then by value in Ascending order (for my items) 
bool asc_price_val(Item a, Item b) {
    if (a.price == b.price) 
        return a.value < b.value;
    else
        return a.price < b.price;
}

//Descending order of the previous (for their items)
bool desc_price_val(Item a, Item b) {
    return !comp_ascending(a,b);
}

void find_best_trades(std::vector<Item>& my_items, std::vector<Item>& their_items){

    //sort my items by value and price, least-valued first
    std::sort(my_items.begin(), my_items.end(), asc_price_val);

    //sort their items by value and price in descending order
    std::sort(their_items.begin(), their_items.end(), desc_price_val);

    //Iterate over my items
    for (auto my_it = my_items.begin(); my_it != my_items.end(); ++my_it) {

        //Use binary search here on their items, in order to quickly search
        //an item with the same price. If you don't find the same price,
        //then keep trying to find a smaller price
        auto theirs = find_best_valued_item_by_price(my_it->price, their_items);

        auto delta_value = theirs->value - my_it->value;
        auto delta_overpaid = my_it->price - theirs->price;

        //Check if this trade worths the overpaid;
        //According to your comments, if you lose 90 in price,
        //you at least need to gain 90 in value
        if (delta_value >= delta_overpaid) {
            trade(my_it, their);
        } 
    }
}

Il tempo per questo sarà O (n log n) per gli ordinamenti, e idealmente O (n log n) per trovare i migliori scambi (ogni elemento nella mia lista, con una ricerca binaria per un elemento nella loro lista).