ProblemaMochila

' Gambas class file

Private almacen As New Elemento[]
Private mochila As New Elemento[]
Private pesomaximo As Float
Private hestrategia As String

Private tmpMochila As New Elemento[] 'mochila temporal para método backtracking
Private valorMaximo As Float

Public Sub _new(pm As Float, estra As String) '' pm: peso maximo que soporta la mochila

  pesomaximo = pm
  hestrategia = estra
  cargaDatos()

End

Public Sub cargaDatos()

  Dim elementoTmp As Elemento
  elementoTmp = New Elemento("TV", 300, 15)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("PS3", 100, 3)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("Libro Java", 10, 1)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("DVD", 5, 0.5)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("Blu-Ray", 50, 0.5)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("Balon", 30, 0.5)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("ipod", 150, 1)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("Printer", 20, 4)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("VideoBeam", 200, 4)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("Laptop", 20, 3)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("ipad", 150, 2)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("PC", 100, 5)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

  elementoTmp = New Elemento("BlackBerry", 150, 0.5)
  elementoTmp.estrategia = hestrategia
  almacen.Add(elementoTmp)

End

Public Sub mostrarMochila()

  Dim pesomochila As Integer = 0
  Dim valorMochila As Float = 0
  Dim elementoTmp As Elemento

  For Each elementoTmp In mochila
    Print elementoTmp.toString()
    pesomochila += elementoTmp.peso
    valorMochila += elementoTmp.valor

  Next
  Print "-------------"
  Print "Peso: ", pesomochila
  Print "Valor: ", valorMochila

End
'-------------------------------------------------------------

'

Public Sub resolverProblema()

  Dim pesomochila As Float = 0
  Dim posicion As Integer = 0
  Dim tmp As Elemento
  'ordenar los elementos del almacen por el valor
  almacen.Sort()

  While ((pesomochila < pesomaximo) And (posicion < almacen.Count))
    tmp = almacen[posicion]
    If (pesomochila + tmp.peso <= pesomaximo) Then
      mochila.Add(tmp)
      pesomochila += tmp.peso
    Endif
    posicion += 1

  Wend

End

'-----------------------------
'resolver por backtraking
'-----------------------------------
Public Sub resolverProblemaBT(posicion As Integer)

  Dim pesomochila As Float = getPeso(tmpMochila)
  Dim valorMochila As Float = getValor(tmpMochila)
  Dim e As Elemento

  If posicion >= almacen.count Then
    If valorMochila > valorMaximo Then
      valorMaximo = valorMochila
      mochila.Clear()
      Copia(tmpMochila, mochila)
    Endif

    Return
  Endif

  e = almacen[posicion]

  If ((pesomochila + e.peso) <= pesomaximo) Then
    tmpMochila.Add(e)
    resolverProblemaBT(posicion + 1)
    Try tmpMochila.remove(tmpMochila.Find(e))
  Endif

  resolverProblemaBT(posicion + 1)

End

Public Function getPeso(tmp As Elemento[]) As Float

  Dim respuesta As Float = 0
  Dim elementoTmp As Elemento

  For Each elementotmp In tmp
    respuesta += elementotmp.peso
  Next

  Return respuesta

End

Public Function getValor(tmp As Elemento[]) As Float

  Dim respuesta As Float = 0
  Dim elementoTmp As Elemento

  For Each elementotmp In tmp
    respuesta += elementoTmp.valor
  Next

  Return respuesta

End

Public Sub Copia(tmp As Elemento[], tmp2 As Elemento[])

  Dim elementoTmp As Elemento

  For Each elementotmp In tmp
    tmp2.Add(elementoTmp)
  Next


End