Programación dinámica

Question

Nunca tuve que lidiar con el DP.
Tenemos N piedras con pesos W_1, ..., W_N. Se necesita dividir todas las piedras por 2 partes, esa diferencia entre ellas fue mínima.

Como hemos n = 6, y el peso = 1,4,5,6,7,9 entonces diferencia es 0.

#include <iostream> 

using namespace std; 

int main() 
{ 
    int  n; // numbers of stones 
    int* a; // array of weights 
    int diff=0; 
    cin >> n; 
    a = new int[n]; 
    for(int i=0;i<n;i++) 
     cin >> a[i]; 

    // And I don't know what's next 

    delete[] a; 
    system("PAUSE"); 
    return 0; 
} 

Answer 1

La idea de la Programación Dinámica es calcular la respuesta de manera iterativa, en cada paso, utilizando las respuestas ya calculadas en pasos anteriores. Vamos a ver cómo esto podría ser implementado para su problema:

Let sum sea la suma de todos los elementos:

int sum = 0; 
for(int i = 0; i < n; ++i) 
    sum += a[ i ]; 

Vamos a construir un conjunto reachable, que contiene todas las sumas posibles que se pueden lograr en una sola pieza :

std::set<int> reachable; 
for(int i = 0; i < n; ++i) 
{ 
    for(set<int>::iterator it = reachable.begin(); it != reachable.end(); ++it) 
     reachable.insert(*it + a[ i ]); 
    reachable.insert(a[ i ]); 
} 

Nota cómo funciona DP aquí: que ya ha construido todas las sumas posibles que se pueden conseguir usando primeras i - 1 piedras que tratamos de añadir i piedra -th a cada uno de t dobladillo para obtener las mismas sumas posibles para i piedras.También agregamos el peso si i -ésima piedra para el conjunto después de el lazo para evitar obtener un peso imposible a[ i ] + a[ i ] (porque cada piedra se puede usar como máximo una vez). Después de este paso obtenemos todos los pesos posibles formados con cada piedra utilizada a lo sumo una vez.

Obviamente, si el peso de una pieza es *it (uno de los elementos establecidos), entonces el peso de la otra parte será sum - *it, por lo que su diferencia será fabs(sum - 2 * (*it)). Busquemos ese mínimo:

diff = sum; // maximal difference, when all stones are in one part 
for(set<int>::iterator it = reachable.begin(); it != reachable.end(); ++it) 
    diff = min(diff, fabs(sum - 2 * (*it))); 
std::cout << "The answer is " << diff << std::endl; 

Answer 2

1 - Si está codifican para ACM, evitar la asignación dinámica/new. Es más lento y es una fuente de segfaults. Trate de asignar estáticamente todo mirando los límites de la declaración del problema.

2 - El problema que desea resolver es el problema de la mochila. Si lo desea, puede encontrar toneladas de recursos y soluciones en Internet/Wikipedia ahora.

3 - El trato con DP es utilizar la caché solo para calcular los valores de una función recursiva una vez. En su caso, tiene 2^n posibles spplitings de las piedras, pero suponiendo que cada piedra es de peso máximo W, solo hay n * W pesos para un conjunto de piedras.

Entonces, ¿podemos hacer una función F (w) que determina si hay un conjunto de piedras en el que se suman w? Si es así, podemos encontrar un algoritmo con solo n * W iteraciones en lugar de 2^n!

¡La respuesta es sí! Pero probablemente necesites ordenar algo para que funcione. Sea G (w, n) se define por:

G(w, n) = 
    (true, s) if there is some set s containing only from the first n stones 
       that adds up to w 
    (false, _) if there is no such set. 

Todo lo que tenemos que hacer ahora es de cómputo G (w, NROCKS) para encontrar F (w)!

Es fácil encontrar una definición recursiva que nos permite calcular G:

G(0, 0) = (true, {}) 
G(W, 0) = (false, _) 
G(W, N) = 
    G(W, N-1) //we don't use the N-th rock - 
       //find solution with remaining rocks instead. 
    OR G(W - w(N), N-1) //if we use the N-th rock, assumin its wheigh is given by w(N) 
         //our problem reduces to seeing if it is possible to add up to 
         // W - w(N) using only the remaining rocks 

Mientras que usted podría aplicar directamente esta función, todavía tendría un tiempo de ejecución exponencial (I won'texplain esto Pero. pensar en el ejemplo de la función tradicional de Fibonacci).

El truco con DP, es exactamente notar que hay un número limitado de entradas que alguna vez utilizaremos para esta función (W de 0 a NROCKS * max (MAXWEIGHT) y N de 0 a NROCKS), para que podamos usar una matriz NROCKS * MAXWEIGHT by NROCKS (o algo similar) como una tabla de búsqueda para evitar el cálculo dos veces.