suma de programación dinámica

Question

¿Cómo utilizaría la programación dinámica para encontrar la lista de enteros positivos en una matriz cuya suma es la más cercana pero no igual a un entero positivo K?

Estoy un poco atascado pensando en esto.

Answer 1

El fraseo habitual para esto es que está buscando el valor más cercano, pero no superior a K. Si quiere decir "menor que K", significa que su valor de K es uno mayor que el habitual. Si realmente quiere decir simplemente "no igual a K", entonces básicamente ejecutaría el algoritmo dos veces, una vez encontrando la suma más grande menor que K, luego encontrando la suma más pequeña mayor que K, y luego escogiendo la que tiene un valor absoluto. la diferencia de K es la más pequeña.

Por el momento voy a suponer que realmente significa la mayor suma menor o igual a K, ya que esa es la formulación más común, y las otras posibilidades realmente no tienen mucho efecto sobre el algoritmo.

La idea básica es bastante simple, aunque (al menos potencialmente) utiliza una gran cantidad de almacenamiento. Construimos una tabla con columnas K + 1 y N + 1 filas (donde N = número de entradas). Inicializamos la primera fila de la tabla en 0.

Luego comenzamos a caminar por la tabla y construimos el mejor valor posible para cada posible valor máximo hasta el máximo real, yendo fila por fila, así que comenzamos con una sola entrada, luego dos entradas posibles, luego tres , y así. En cada punto de la tabla, solo hay dos posibilidades para obtener el mejor valor: el mejor valor anterior que no usa la entrada actual, o bien la entrada actual más el mejor valor anterior para el máximo menos la entrada actual (y desde calculamos los valores de la tabla en orden, siempre tendremos ese valor).

También, por lo general, deseamos realizar un seguimiento de los elementos que realmente se utilizaron para producir el resultado. Para hacer eso, configuramos un booleano para un punto dado en la tabla como verdadero si y solo si calculamos un valor para ese punto en la tabla usando la nueva entrada para esa fila (en lugar de simplemente copiar el mejor valor de la fila anterior). El mejor resultado está en la esquina inferior derecha, así que comenzamos allí y caminamos hacia atrás por la mesa una fila a la vez. Cuando llegamos a una fila donde el booleano para esa columna se estableció en verdadero, sabemos que encontramos una entrada que se utilizó. Imprimimos ese artículo, y luego lo restamos del total para obtener la siguiente columna a la izquierda, donde encontraremos la siguiente entrada que se usó para producir esta salida.

Aquí hay una implementación que está técnicamente en C++, pero escrita principalmente en estilo C para que cada paso sea lo más explícito posible.

#include <iostream> 
#include <functional> 

#define elements(array) (sizeof(array)/sizeof(array[0])) 

int main() { 

    // Since we're assuming subscripts from 1..N, I've inserted a dummy value 
    // for v[0]. 
    int v[] = {0, 7, 15, 2, 1}; 

    // For the moment I'm assuming a maximum <= MAX. 
    const int MAX = 17; 

    // ... but if you want to specify K as the question implies, where sum<K, 
    // you can get rid of MAX and just specify K directly: 
    const int K = MAX + 1; 

    const int rows = elements(v); 

    int table[rows][K] = {0}; 
    bool used[rows][K] = {false}; 

    for (int i=1; i<rows; i++) 
     for (int c = 0; c<K; c++) { 
      int prev_val = table[i-1][c]; 
      int new_val; 

      // we compute new_val inside the if statement so we won't 
      // accidentally try to use a negative column from the table if v[i]>c 
      if (v[i] <= c && (new_val=v[i]+table[i-1][c-v[i]]) > prev_val) { 
       table[i][c] = new_val; 
       used[i][c] = true; 
      } 
      else 
       table[i][c] = prev_val; 
     } 

    std::cout << "Result: " << table[rows-1][MAX] << "\n"; 
    std::cout << "Used items where:\n"; 
    int column = MAX; 
    for (int i=rows; i>-1; i--) 
     if (used[i][column]) { 
      std::cout << "\tv[" << i << "] = " << v[i] << "\n"; 
      column -= v[i]; 
     } 

    return 0; 
} 

Hay un par de cosas que normalmente optimizar en este (que yo no tengo para facilitar la lectura).Primero, si alcanza una suma óptima, puede dejar de buscar, por lo que en este caso podríamos salir del ciclo antes de considerar la entrada final de 1 (dado que 15 y 2 dan el resultado deseado de 17).

En segundo lugar, en la tabla solo utilizamos dos filas en un momento dado: una fila actual y una fila anterior. Las filas anteriores (en la tabla principal) nunca se vuelven a utilizar (es decir, para calcular la fila [n] necesitamos los valores de row[n-1], pero no row[n-2], row[n-3], ... row[0]. Para reducir el almacenamiento, podemos hacer que tabla solo dos filas, e intercambiamos entre la primera y la segunda fila. Un truco muy parecido a C para hacer eso sería usar solo el bit menos significativo del número de fila, por lo que reemplazaría table[i] y table[i-1] con table[i&1] y table[(i-1)&1] respectivamente (pero sólo para la mesa principal - no al dirigirse a la mesa used

Answer 2

Aquí se muestra un ejemplo en Python:

def closestSum(a,k): 
    s={0:[]} 
    for x in a: 
    ns=dict(s) 
    for j in s: 
     ns[j+x]=s[j]+[x] 
    s=ns 
    if k in s: 
    del s[k] 
    return s[min(s,key=lambda i:abs(i-k))] 

Ejemplo:

>>> print closestSum([1,2,5,6],10) 
[1, 2, 6] 

La idea es simplemente hacer un seguimiento de qué cantidades se pueden hacer de todos los elementos anteriores a medida que avanza a través de la matriz , así como una forma de hacer esa suma. Al final, solo elige lo más cercano a lo que quieres. Es una solución de programación dinámica porque divide el problema global en subproblemas y utiliza una tabla para recordar los resultados de los subproblemas en lugar de volver a calcularlos.

Answer 3

idea de Cato en la raqueta:

#lang racket 
(define (closest-sum xs k) 
    (define h (make-hash '([0 .()]))) 
    (for* ([x xs] [(s ys) (hash-copy h)]) 
    (hash-set! h (+ x s) (cons x ys)) 
    (hash-set! h x (list x))) 
    (when (hash-ref h k #f) (hash-remove! h k)) 
    (cdr (argmin (λ (a) (abs (- k (car a)))) (hash->list h)))) 

.

Para obtener un programa aún más concisa, uno puede agarrar terse-hash.rkt de GitHub y escribir:

(define (closest-sum xs k) 
    (define h {make '([0 .()])}) 
    (for* ([x xs] [(s ys) {copy h}]) 
    {! h (+ x s) (cons x ys)} 
    {! h x (list x)}) 
    (when {h k #f} {remove! h k}) 
    (cdr (argmin (λ (a) (abs (- k (car a)))) {->list h})))