Problema de la mochila en lenguaje C 01, ¿quién puede explicarlo brevemente?

01 El problema de la mochila es que hay una bolsa con una capacidad de W, y luego hay un montón de artículos (1...n), donde wi y vi son el peso y el valor de la i-ésimo artículo respectivamente. Ahora necesitamos encontrar. El objetivo es hacer que los artículos en la bolsa sean lo más valiosos posible. Entonces, si este artículo se coloca en la bolsa corresponde al valor 0 o 1. El algoritmo es programación dinámica y necesita demostrar las propiedades óptimas de la subestructura. Utilice s[i][j] para representar el valor máximo que se puede obtener cuando solo existen los primeros i elementos y la capacidad de contención es j, y existe una fórmula recursiva

s[i][j] j]= s[i- 1][j], wi>j

max{s[i-1][j],s[i-1][j-wi]+vi}, wi<=j

s[0][j]=0 1<=j<=W

s[i][0]=0 1<=i<=n

Entonces, no importa qué lenguaje se use para implementarlo, es calcular la fórmula anterior y finalmente obtener s [n] [W]. La fórmula anterior se puede implementar fácilmente mediante recursividad. arriba, es decir, dos capas para usted También puede usar la pila para implementar de arriba hacia abajo, este es un método basado en registros.

La W anterior sólo considera números enteros.