raggruppare oggetti casualmente ma peso totale costante

[l***@gmail.com]

Ciao a tutti.
Immaginiamo di avere un elenco di oggetti con relativo peso (ad esempio inserito in una matrice n x 2, nella prima colonna ci sono gli identificativi degli oggetti, e nella seconda il relativo peso).
Vorrei scrivere una funzione che prenda ogni volta degli oggetti a caso da questo elenco, anche in numero diverso, però il cui peso totale sia SEMPRE uguale a TOT.

Qualche suggerimento su come potrei impostare la cosa?
Grazie.

[Jack]

Post by l***@gmail.com
Ciao a tutti.
Immaginiamo di avere un elenco di oggetti con relativo peso (ad esempio inserito in una matrice n x 2, nella prima colonna ci sono gli identificativi degli oggetti, e nella seconda il relativo peso).
Vorrei scrivere una funzione che prenda ogni volta degli oggetti a caso da questo elenco, anche in numero diverso, però il cui peso totale sia SEMPRE uguale a TOT.
Qualche suggerimento su come potrei impostare la cosa?
Grazie.

immagino che tu possa usare uno degli algoritmi che il tuo professore ha descritto in classe.

Ciao Jack

[f***@gmail.com]

Post by l***@gmail.com
Ciao a tutti.
Immaginiamo di avere un elenco di oggetti con relativo peso (ad esempio
inserito in una matrice n x 2, nella prima colonna ci sono gli
identificativi degli oggetti, e nella seconda il relativo peso).
Vorrei scrivere una funzione che prenda ogni volta degli oggetti a caso
da questo elenco, anche in numero diverso, però il cui peso totale sia
SEMPRE uguale a TOT.

E' un subset sum, che come sai è uno dei 21 problemi NP completi di Karp.


Ciao!

[_merlinO_]

E' un subset sum, che come sai Ú uno dei 21 problemi NP completi di

Karp.

Senza saperne nulla ho pensato a come si potrebbe risolvere, penso che con
una funzione ricorsiva non sarebbe difficile. Magari non sarebbe la più
efficiente ma risolverebbe. Immagino però ci siano soluzioni più
raffinate...

[dacav]

Post by _merlinO_

E' un subset sum, che come sai Ú uno dei 21 problemi NP completi di

Karp.
Senza saperne nulla ho pensato a come si potrebbe risolvere, penso che con
una funzione ricorsiva non sarebbe difficile. Magari non sarebbe la più
efficiente ma risolverebbe. Immagino però ci siano soluzioni più
raffinate...

Sicuramente è risolvibile. Essendo però un NP-Completo,
l'efficienza va a rotoli, garantito. E se riesci a renderlo
efficiente sei milionario.

https://en.wikipedia.org/wiki/P_versus_NP_problem

[f***@gmail.com]

Post by _merlinO_

E' un subset sum, che come sai Ú uno dei 21 problemi NP completi di

Karp.
Senza saperne nulla ho pensato a come si potrebbe risolvere, penso che con
una funzione ricorsiva non sarebbe difficile. Magari non sarebbe la più
efficiente ma risolverebbe. Immagino però ci siano soluzioni più
raffinate...

Il problema in oggetto, che è NP-completo debole, può essere risolto in
tempo pseudo-polinomiale con una implementazione DP. Esiste anche un
algoritmo approssimato (e che quindi non trova sempre la soluzione ottima)
che corre in tempo polinomiale.

Il "difficile" di solito è solo riconoscere il problema: fatto questo la
letteratura in merito a questo tipo di problemi è sconfinata :)


Ciao!

[LutherBlissett]

Post by _merlinO_
Senza saperne nulla ho pensato a come si potrebbe risolvere, penso che con
una funzione ricorsiva non sarebbe difficile. Magari non sarebbe la più
efficiente ma risolverebbe. Immagino però ci siano soluzioni più
raffinate...

Con la ricorsione sempre occhio agli stack overflow...

[dacav]

Post by LutherBlissett
Con la ricorsione sempre occhio agli stack overflow...

E quando giri su stack overflow, sempre occhio alle domande sulla
ricorsione :P

Scusa, non ho resistito.

[LutherBlissett]

Post by dacav

Post by LutherBlissett
Con la ricorsione sempre occhio agli stack overflow...

E quando giri su stack overflow, sempre occhio alle domande sulla
ricorsione :P
Scusa, non ho resistito.

:-)