Sommario programmazione dinamica

Question

Come utilizzare la programmazione dinamica per trovare l'elenco di numeri interi positivi in ​​un array la cui somma è più vicina ma non uguale a qualche intero positivo K?

Sono un po 'bloccato pensando a questo.

Answer 1

Il solito fraseggio per questo è che stai cercando il valore più vicino, ma non superiore a K. Se intendi "meno di K", significa semplicemente che il tuo valore di K è maggiore del solito. Se intendi veramente solo "non uguale a K", in pratica eseguirai due volte l'algoritmo, una volta che trovi la somma più grande minore di K, quindi trovi nuovamente la somma più piccola maggiore di K, quindi scegli quella di quelli la cui assoluta la differenza da K è la più piccola.

Per il momento assumerò che tu intenda veramente la somma più grande minore o uguale a K, poiché questa è la formulazione più comune e le altre possibilità non hanno molto effetto sull'algoritmo.

L'idea di base è abbastanza semplice, anche se (almeno potenzialmente) utilizza molta memoria. Costruiamo una tabella con K + 1 colonne e N + 1 righe (dove N = numero di ingressi). Inizializziamo la prima riga della tabella su 0.

Poi iniziamo a camminare attraverso il tavolo, e costruendo il miglior valore possibile per ogni possibile valore massimo fino al massimo reale, andando riga per riga quindi iniziamo con un solo input, quindi due possibili input, quindi tre , e così via. In ogni punto della tabella ci sono solo due possibilità per il miglior valore: il valore migliore precedente che non utilizza l'ingresso corrente, oppure l'ingresso corrente più il precedente valore migliore per il massimo meno l'ingresso corrente (e dal calcoliamo i valori della tabella in ordine, avremo sempre questo valore).

Inoltre, di solito vogliamo tenere traccia di quali elementi sono stati effettivamente utilizzati per produrre il risultato. Per fare ciò, impostiamo un Booleano per un dato punto nella tabella su true se e solo se calcoliamo un valore per quel punto nella tabella usando il nuovo input per quella riga (piuttosto che semplicemente copiando il valore migliore della riga precedente). Il risultato migliore è nell'angolo in basso a destra, quindi iniziamo lì e camminiamo all'indietro attraverso il tavolo una riga alla volta. Quando arriviamo a una riga in cui il booleano per quella colonna è stato impostato su true, sappiamo che abbiamo trovato un input che è stato utilizzato. Stampiamo quell'articolo e poi lo sottraggiamo dal totale per ottenere la colonna successiva a sinistra dove troveremo l'input successivo che è stato usato per produrre questo output.

Ecco un'implementazione tecnicamente in C++, ma scritta principalmente in stile C per rendere ogni passaggio il più esplicito possibile.

#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; 
} 

Ci sono un paio di cose che normalmente si ottimizzare in questo (che non ho per motivi di leggibilità).Innanzitutto, se raggiungi una somma ottimale, puoi interrompere la ricerca, quindi in questo caso potremmo interrompere il ciclo prima di considerare l'input finale di 1 (dal 15 e 2 fornire il risultato desiderato di 17).

In secondo luogo, nella tabella stessa usiamo solo due righe in un dato momento: una riga corrente e una riga precedente. Le righe precedenti (nella tabella principale) non vengono mai più utilizzate (ad esempio, per calcolare la riga [n] sono necessari i valori da row[n-1], ma non da row[n-2], row[n-3], ... row[0]. Per ridurre lo spazio di archiviazione, possiamo rendere il principale tabella essere solo due righe e scambiamo tra la prima e la seconda riga. Un trucco molto simile a C sarebbe quello di utilizzare solo il bit meno significativo del numero di riga, quindi sostituirai table[i] e table[i-1] con table[i&1] e rispettivamente table[(i-1)&1] (ma solo per la tabella principale - non quando si affronta la tabella used

Answer 2

Ecco un esempio in pitone:

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))] 

Esempio:

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

L'idea è semplicemente per tenere traccia di quello somme può essere fatto da tutti gli elementi precedenti come si passa attraverso l'array , così come un modo per fare quella somma. Alla fine, scegli il più vicino a quello che vuoi. È una soluzione di programmazione dinamica perché rompe il problema generale in sotto-problemi e utilizza una tabella per ricordare i risultati dei sotto-problemi invece di ricalcolarli.

Answer 3

idea di Catone in Racket:

#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)))) 

.

Per ottenere un programma ancora terser, si può afferrare terse-hash.rkt da GitHub e scrivere:

(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})))