0/1 problema knapsack de programación dinámica-implementación java

El problema de programación dinámica es adecuado para resolver el problema óptimo de la solución, como el problema de la mochila 0/1.
Un ejemplo específico del problema de la mochila: Supongamos que hay una mochila existente con una capacidad de 10 kg, y hay otros tres artículos, a saber, a1, a2 y a3. El peso del artículo a1 es de 3kg y el valor es 4; el peso del artículo a2 es de 4kg y el valor es 5; el peso del artículo a3 es de 5kg y el valor es 6. ¿Qué artículos se deben poner en la mochila para maximizar el valor total de la mochila?
Este problema puede lograrse mediante el método exhaustivo, pero cuando el número es grande, el método exhaustivo es obviamente inapropiado.
En primer lugar, modelar matemáticamente este problema. Para a1, a2… un artículo, sus pesos son w1, w2… wn, y sus valores son q1, q1… Qn. Cómo poner los artículos hace que el valor de los artículos debajo de la mochila más.
Podemos suponer que hemos obtenido el valor máximo de c[i-1][m-wi], a continuación, para c[i][m], ¿se considera el elemento i-th actual? La cuestión de si poner en una mochila. Esto da como resultado la fórmula matemática:
C[i][m]=max{c[i-1][m-w[i]]+pi , c[i-1][m]}
Así que lo que tenemos que hacer a continuación es implementar esta fórmula matemática. código mostrar como se muestra a continuación:

package com.wsy.dynamic;

public class Dynamic01 {
    public static void main(String[] args) {
        int m = 10;
        int[] w = new int[]{3,4,5};
        int[] q = new int[]{4,5,6};
        int[][] c = new int[w.length+1][m+1];
        //Initialization, the first step of dynamic programming is to initialize the boundary value
        for(int i = 0;i<w.length;i++){
            c[i][0] = 0;
        }
        for(int i = 0;i<m;i++){
            c[0][i] = 0;
        }
        for(int i = 1;i<=w.length;i++){
            for(int j = 1;j<=m;j++){
                if(j>=w[i-1]){
                if(c[i-1][j-w[i-1]] + q[i-1]>c[i-1][j]){
                    c[i][j] = c[i-1][j-w[i-1]] + q[i-1];
                }else{
                    c[i][j] = c[i-1][j];
                }
                }else{
                    c[i][j] = c[i-1][j];
                }

            }
        }
        System.out.println(c[3][10]);
    }
}

Hay un paso de inicialización en el código y cualquier problema de programación dinámica debe inicializar el límite. Así que el problema de programación dinámica se puede hacer en tres pasos
1 Modelado matemático, para obtener fórmulas matemáticas, tales como: c[i][m]=max{c[i-1][mw[i]]+pi, c[i -1][m]}
2 Escribir código para implementar algoritmos. Los algoritmos de programación dinámicos a menudo tienen un marco unificado
2.1: Inicializar las condiciones límite
2.2: para el recorrido de bucle para una solución óptima
El marco de trabajo del algoritmo es el siguiente:

for(j=1; j<=m; j=j+1) // the first stage
       xn[j] = initial value;

 for(i=n-1; i>=1; i=i-1)// other n-1 stages
   for(j=1; j>=f(i); j=j+1)//f(i) expression related to i
     xi[j]=j=max(ormin）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};

t = g(x1[j1:j2]); // Solve the optimal solution of the entire problem from the optimal solution of the sub-problem

print(x1[j1]);

for(i=2; i<=n-1; i=i+1）
{  
     t = t-xi-1[ji];

     for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
}