java - tienda - ¿Cómo puedo resolverlo? KnapSack-valores todos iguales pero cada otro objeto tiene tres pesos

programa de ventas en java

Question

Tengo un problema para resolver mi ejercicio. Leí sobre programación dinámica y algoritmos y creo que mi ejercicio es un "problema específico de mochila". Lo resolví con el método de fuerza bruta, pero no puedo resolverlo con programación dinámica.

Tengo un barco (mochila) que tiene 300 toneladas de peso. Hay cristales que tienen en sí mismas 3 sustancias (X, Y, Z): cada otra sustancia tiene peso y todos los cristales tienen el mismo valor. Necesito embalar para enviar tantos cristales como sea posible, pero la proporción de sustancias de todos los cristales compactos debe ser de 1: 1: 1. Pero, por ejemplo, si tengo tres cristales con proporciones 1: 1: 1 que dan la mayor cantidad de toneladas y ocho cristales que dan el mismo número de toneladas (otras dos combinaciones de cristales dan la mayor cantidad de toneladas), tengo que elegir combinaciones con el menor número de cristales.

Lo resolví con el método de fuerza bruta: creé una lista de matrices de todas las combinaciones. Luego encontré combinaciones con proporciones de 1: 1: 1. Luego encontré la combinación que da el mayor número de toneladas y tiene la menor cantidad de cristales (si hay dos o más combinaciones con la misma cantidad de toneladas). Revisé las pruebas y me arrojaron buenos puntajes, no tengo idea de cómo puedo resolverlo con programación dinámica; / ¿Hay alguien que me ayude?

Por ejemplo, cuando tengo 10 cristales:

 1) X =2 Y =3 Z =4
 2) X =5 Y=10 Z =2
 3) X =3 Y =3 Z =3
 4) X =1 Y =0 Z =6
 5) X =9 Y=12 Z =4
 6) X =1 Y =1 Z =1
 7) X =2 Y =1 Z=0
 8) X =1 Y =2 Z =3
 9) X =1 Y =1 Z =1
10) X =4 Y =3 Z =3

La solución es: máx. 27 toneladas con cinco cristales (números: 1, 3, 6, 7 y 9)

Answer 1

Hay algunos buenos tutoriales en Internet que explican a fondo el problema de la mochila.

Más específicamente, recomendaría este específico , donde el problema y el enfoque DP se explican por completo, incluida la solución en tres idiomas diferentes (incluido Java).

// A Dynamic Programming based solution for 0-1 Knapsack problem
class Knapsack
{
    // A utility function that returns maximum of two integers
    static int max(int a, int b) { return (a > b)? a : b; }

   // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSack(int W, int wt[], int val[], int n)
    {
         int i, w;
     int K[][] = new int[n+1][W+1];

     // Build table K[][] in bottom up manner
     for (i = 0; i <= n; i++)
     {
         for (w = 0; w <= W; w++)
         {
             if (i==0 || w==0)
                  K[i][w] = 0;
             else if (wt[i-1] <= w)
                   K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
             else
                   K[i][w] = K[i-1][w];
         }
      }

      return K[n][W];
    }

    // Driver program to test above function
    public static void main(String args[])
    {
        int val[] = new int[]{60, 100, 120};
        int wt[] = new int[]{10, 20, 30};
        int  W = 50;
        int n = val.length;
        System.out.println(knapSack(W, wt, val, n));
    }
}
/*This code is contributed by Rajat Mishra */

Fuente: GeeksForGeeks