Geek asks and answers

Dynamic Programming Amount

How would you use dynamic programming to find a list of positive integers in an array whose sum is closest but not equal to some positive number K?

I got a little stuck thinking about it.

+5
source share
3 answers

The usual phrase for this is that you are looking for the value closest to, but not exceeding K. If you mean "less than K", it means that your K value is greater than usual. If you really mean just “not equal to K,” then you basically run the algorithm twice as soon as you find the largest amount less than K, then again find the smallest amount greater than K, then choose one that is completely different from K is the smallest.

At the moment, I'm going to assume that you really mean the largest amount, less than or equal to K, since the most common wording and other features do not really have a big impact on the algorithm.

, ( ) . K + 1 N + 1 ( N = ). 0.

, , , , , , . : , , ( , ).

, . Boolean true , , ( ). - , . , Boolean true, , , . , , , , .

++, C, .

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

, ( ). -, , , , 1 ( 15 2 17).

-, : . ( ) (.. [n] row[n-1], row[n-2], row[n-3],... row[0]. , , . , C, , , d table[i] table[i-1] table[i&1] table[(i-1)&1] ( - used.

+6

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

:

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

, , , . , . , - .

+3

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

, terse-hash.rkt GitHub :

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

More articles:


All Articles