Advertisement
jsbsan

ProblemaMochila

May 23rd, 2014
5,576
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ' Gambas class file
  2.  
  3. Private almacen As New Elemento[]
  4. Private mochila As New Elemento[]
  5. Private pesomaximo As Float
  6. Private hestrategia As String
  7.  
  8. Private tmpMochila As New Elemento[] 'mochila temporal para método backtracking
  9. Private valorMaximo As Float
  10.  
  11. Public Sub _new(pm As Float, estra As String) '' pm: peso maximo que soporta la mochila
  12.  
  13.   pesomaximo = pm
  14.   hestrategia = estra
  15.   cargaDatos()
  16.  
  17. End
  18.  
  19. Public Sub cargaDatos()
  20.  
  21.   Dim elementoTmp As Elemento
  22.   elementoTmp = New Elemento("TV", 300, 15)
  23.   elementoTmp.estrategia = hestrategia
  24.   almacen.Add(elementoTmp)
  25.  
  26.   elementoTmp = New Elemento("PS3", 100, 3)
  27.   elementoTmp.estrategia = hestrategia
  28.   almacen.Add(elementoTmp)
  29.  
  30.   elementoTmp = New Elemento("Libro Java", 10, 1)
  31.   elementoTmp.estrategia = hestrategia
  32.   almacen.Add(elementoTmp)
  33.  
  34.   elementoTmp = New Elemento("DVD", 5, 0.5)
  35.   elementoTmp.estrategia = hestrategia
  36.   almacen.Add(elementoTmp)
  37.  
  38.   elementoTmp = New Elemento("Blu-Ray", 50, 0.5)
  39.   elementoTmp.estrategia = hestrategia
  40.   almacen.Add(elementoTmp)
  41.  
  42.   elementoTmp = New Elemento("Balon", 30, 0.5)
  43.   elementoTmp.estrategia = hestrategia
  44.   almacen.Add(elementoTmp)
  45.  
  46.   elementoTmp = New Elemento("ipod", 150, 1)
  47.   elementoTmp.estrategia = hestrategia
  48.   almacen.Add(elementoTmp)
  49.  
  50.   elementoTmp = New Elemento("Printer", 20, 4)
  51.   elementoTmp.estrategia = hestrategia
  52.   almacen.Add(elementoTmp)
  53.  
  54.   elementoTmp = New Elemento("VideoBeam", 200, 4)
  55.   elementoTmp.estrategia = hestrategia
  56.   almacen.Add(elementoTmp)
  57.  
  58.   elementoTmp = New Elemento("Laptop", 20, 3)
  59.   elementoTmp.estrategia = hestrategia
  60.   almacen.Add(elementoTmp)
  61.  
  62.   elementoTmp = New Elemento("ipad", 150, 2)
  63.   elementoTmp.estrategia = hestrategia
  64.   almacen.Add(elementoTmp)
  65.  
  66.   elementoTmp = New Elemento("PC", 100, 5)
  67.   elementoTmp.estrategia = hestrategia
  68.   almacen.Add(elementoTmp)
  69.  
  70.   elementoTmp = New Elemento("BlackBerry", 150, 0.5)
  71.   elementoTmp.estrategia = hestrategia
  72.   almacen.Add(elementoTmp)
  73.  
  74. End
  75.  
  76. Public Sub mostrarMochila()
  77.  
  78.   Dim pesomochila As Integer = 0
  79.   Dim valorMochila As Float = 0
  80.   Dim elementoTmp As Elemento
  81.  
  82.   For Each elementoTmp In mochila
  83.     Print elementoTmp.toString()
  84.     pesomochila += elementoTmp.peso
  85.     valorMochila += elementoTmp.valor
  86.    
  87.   Next
  88.   Print "-------------"
  89.   Print "Peso: ", pesomochila
  90.   Print "Valor: ", valorMochila
  91.  
  92. End
  93. '-------------------------------------------------------------
  94.  
  95. '
  96.  
  97. Public Sub resolverProblema()
  98.  
  99.   Dim pesomochila As Float = 0
  100.   Dim posicion As Integer = 0
  101.   Dim tmp As Elemento
  102.   'ordenar los elementos del almacen por el valor
  103.   almacen.Sort()
  104.  
  105.   While ((pesomochila < pesomaximo) And (posicion < almacen.Count))
  106.     tmp = almacen[posicion]
  107.     If (pesomochila + tmp.peso <= pesomaximo) Then
  108.       mochila.Add(tmp)
  109.       pesomochila += tmp.peso
  110.     Endif
  111.     posicion += 1
  112.    
  113.   Wend
  114.  
  115. End
  116.  
  117. '-----------------------------
  118. 'resolver por backtraking
  119. '-----------------------------------
  120. Public Sub resolverProblemaBT(posicion As Integer)
  121.  
  122.   Dim pesomochila As Float = getPeso(tmpMochila)
  123.   Dim valorMochila As Float = getValor(tmpMochila)
  124.   Dim e As Elemento
  125.  
  126.   If posicion >= almacen.count Then
  127.     If valorMochila > valorMaximo Then
  128.       valorMaximo = valorMochila
  129.       mochila.Clear()
  130.       Copia(tmpMochila, mochila)
  131.     Endif
  132.    
  133.     Return
  134.   Endif
  135.  
  136.   e = almacen[posicion]
  137.  
  138.   If ((pesomochila + e.peso) <= pesomaximo) Then
  139.     tmpMochila.Add(e)
  140.     resolverProblemaBT(posicion + 1)
  141.     Try tmpMochila.remove(tmpMochila.Find(e))
  142.   Endif
  143.  
  144.   resolverProblemaBT(posicion + 1)
  145.  
  146. End
  147.  
  148. Public Function getPeso(tmp As Elemento[]) As Float
  149.  
  150.   Dim respuesta As Float = 0
  151.   Dim elementoTmp As Elemento
  152.  
  153.   For Each elementotmp In tmp
  154.     respuesta += elementotmp.peso
  155.   Next
  156.  
  157.   Return respuesta
  158.  
  159. End
  160.  
  161. Public Function getValor(tmp As Elemento[]) As Float
  162.  
  163.   Dim respuesta As Float = 0
  164.   Dim elementoTmp As Elemento
  165.  
  166.   For Each elementotmp In tmp
  167.     respuesta += elementoTmp.valor
  168.   Next
  169.  
  170.   Return respuesta
  171.  
  172. End
  173.  
  174. Public Sub Copia(tmp As Elemento[], tmp2 As Elemento[])
  175.  
  176.   Dim elementoTmp As Elemento
  177.  
  178.   For Each elementotmp In tmp
  179.     tmp2.Add(elementoTmp)
  180.   Next
  181.  
  182.  
  183. End
Advertisement
RAW Paste Data Copied
Advertisement