Algoritmo dello zaino senza limiti in vb.net

[Gpanz]

Come al tempo dei greci, alle volte alcuni demoni ci perseguitano e ci ossessionano finché non facciamo quello che vogliono loro. Specialmente se questo è il demone del programmatore che ti spinge a cercare una soluzione interpretabile da un computer per ogni problema che ci mette davanti la vita.

Così è stato anche in questo caso, dove un dilemma mi era tornato in mente dopo tanto tempo, e non ricordavo se ci fosse o meno una soluzione, ma soprattutto (ed è il peggio) non riuscivo a risolverlo.

Finchè non ho aperto una discussione sul forum, e un utente mi ha detto che si trattava di un problema noto come Algoritmo dello zaino del contrabbandiere (leggete la discussione per avere più dettagli).

Il problema era questo:

Un ladro decide di svaliggiare un negozio di elettrodomestici. Il negozio in questione vende esclusivamente Frigoriferi e Lavatrici

un frigorifero occupa un volume di 1m cubo e costa 1000€

una lavatrice occupa un volume di 0.6m cubi e costa 590€

considerando che il furgone che utilizzerà il ladro ha una capienza di 3.8m cubi e che ha il tempo di fare un solo viaggio prima che arrivi la vigilanza, sviluppare un algoritmo in grado di elencare gli articoli da caricare nel furgone per ottenere il maggior guadagno possibile.

Sono stato circa una settimana a cercare un soluzione elegante a questo problema, ma non ci sono riuscito. Quella che cercavo era una soluzione che non implicasse controllare tutte le possibili combinazioni, un metodo intelligente per conoscere tramite un calcolo la lista di oggetti che il ladro deve rubare.

Ma per fortuna esiste wikipedia (un ringraziamento anche a yronium che mi ha fornito il nome dell'algoritmo) dove ho potuto scoprire che non esiste nessuna soluzione al problema, che non implichi per forza il confronto fra tutte le possibili soluzioni. (meno male stavo già per sentite puzza di neurone bruciato)

a questo punto dovevo solo dare il colpo di grazia al demone. Armato di visual studio e sfinito dall'ossessione, ho incominciato a scrivere...

Per creare le varie combinazioni ho deciso di utilizzare una funzione ricorsiva che aggiunge semplicemente un elemento e verifica se con l'elemento aggiunto siamo ancora entro i limiti del volume masimo (quello del furgone).
A questo punto avrei potuto memorizzare tutte le combinazioni all'interno di un array temporaneo per poi prendere semplicemente la combinazione con valore più grande, ma l'idea non mi piaceva molto

1) perchè dovevo fare due passaggi
2) perchè potrei aver a che fare con un numero smisuratamente enorme di combinazioni, e dove le dovrei memorizzare tutte?(immaginare Ariel di Zelig che dice che il computer si è svampato)

Ho deciso allora di controllare le combinazioni volta per volta memorizzando la combinazione migliore. Sembrava facile, ma devo ammettere che sono stato un decina di minuti a fissare lo schermo senza sapere cosa fare, ma alla file c'è l'ho fatta.

ed ecco la classe :

Public Class AlgZaino

    Public Elementi As New ArrayList
    Public MaxVolume As Decimal

    Public Function Risultato() As ArrayList
        Return ListaElementiValoreMassimo(New ArrayList)
    End Function

    Private Function ListaElementiValoreMassimo(ByVal Lista As ArrayList) As ArrayList
        Dim BestLista As ArrayList = Lista
        For i As Integer = 0 To Elementi.Count - 1
            Dim Lista1 As ArrayList = Lista.Clone
            Lista1.Add(Elementi(i))
            If valLista(Lista1, True) <= MaxVolume Then
                Dim lista2 As ArrayList = ListaElementiValoreMassimo(Lista1)
                If valLista(lista2, False) > valLista(BestLista, False) Then BestLista = lista2
            End If
        Next
        Return BestLista
    End Function

    Private Function valLista(ByVal l As ArrayList, ByVal volume As Boolean) As Decimal
        Dim Tot As Decimal = 0
        For i As Integer = 0 To l.Count - 1
            Tot += valEl(l(i), volume) 'Per i cultori dell'Option Strict utilizzate DirectCast(l(i),Elemento)
        Next
        Return Tot
    End Function

    Private Function valEl(ByVal el As Elemento, ByVal volume As Boolean) As Decimal
        Return IIf(volume, el.Volume, el.Valore)
    End Function

End Class

di seguito la struttura di elemento

Public Class Elemento
    Public Sub New(ByVal Name As String, ByVal Val As Decimal, ByVal Vol As Decimal)
        Nome = Name
        Valore = Val
        Volume = Vol
    End Sub
    Public Nome As String = ""
    Public Valore As Decimal = 0
    Public Volume As Decimal = 0
End Class

a questo punto prendete un form metteteci un button e una label dopo di che:

Public Class Form1

    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

        Dim alg As New AlgZaino

        alg.Elementi.Add(New Elemento("Frigo", 1000, 1))
        alg.Elementi.Add(New Elemento("Lavatrice", 590, 0.6))

        alg.MaxVolume = 3.8

        Dim r As ArrayList = alg.Risultato

        Label1.Text = ""
        For Each El As Elemento In r
            Label1.Text = Label1.Text & El.Nome & Environment.NewLine
        Next

    End Sub
End Class

ma per l'uomo moderno che va sempre di fretta e non ha il tempo di creare un nuovo progetto AlgoritmoZaino.zip


Ovviamente quest'algoritmo può essere impiegato in diversi ambiti e non solo per svaliggiare negozzi.

sarebbe interessante se si elencassero tutti gli ambiti di impiego di questo algoritmo, se vi viene un'idea postatela.

ciao

[yronium]

Accidenti, ho notato solo oggi qs. articolo. Non posso entrare nel merito della programmazione .Net dato che non la conosco, ma penso che tu abbia fatto un buon lavoro affrontando e proponendo una soluzione ad un problema piuttosto diffuso. Ottimo lavoro e grazie per il contributo. Quando poi imparerai anche a scrivere svaligiare con una g sola ti proporrò anche come moderatore.

[alby_net]

Ciao,
complimenti per il buon lavoro fatto, atto a risolvere il problema della combinazione migliore basato sui volumi.

c'è un piccolo problema però, di cui la procedura da te illustrata non tiene conto, ed è che il volume non è sempre occupabile in maniera omogenea. mi spiego meglio.
bisognerebbe tenere conto dell'orientamento degli oggetti come vengono posizionati all'interno del furgone. non so se sono stato chiaro, ma se risolvessi questo di problema sarebbe davvero utile!


ciao