Tổng số lập trình động

Question

Bạn sẽ sử dụng lập trình động như thế nào để tìm danh sách các số nguyên dương trong một mảng có tổng gần bằng nhưng không bằng số nguyên dương K?

Tôi hơi mắc kẹt suy nghĩ về điều này.

Answer 1

Phrasing thông thường cho điều này là bạn đang tìm giá trị gần nhất, nhưng không vượt quá K. Nếu bạn có nghĩa là "nhỏ hơn K", nó chỉ có nghĩa là giá trị của K là lớn hơn bình thường. Nếu bạn thực sự có nghĩa là "không bằng K", thì về cơ bản bạn sẽ chạy qua thuật toán hai lần, khi tìm số tiền lớn nhất nhỏ hơn K, sau đó tìm lại số tiền nhỏ nhất lớn hơn K, sau đó chọn một trong số đó sự khác biệt từ K là nhỏ nhất.

Hiện tại tôi giả sử bạn thực sự có nghĩa là tổng lớn nhất nhỏ hơn hoặc bằng K, vì đó là công thức phổ biến nhất và các khả năng khác không thực sự ảnh hưởng nhiều đến thuật toán.

Ý tưởng cơ bản khá đơn giản, mặc dù nó (ít nhất là có khả năng) sử dụng nhiều bộ nhớ. Chúng tôi xây dựng một bảng với các cột K + 1 và các hàng N + 1 (trong đó N = số đầu vào). Chúng tôi khởi tạo hàng đầu tiên trong bảng thành 0. Sau đó, chúng tôi bắt đầu đi qua bảng và xây dựng giá trị tốt nhất có thể cho mỗi giá trị tối đa có thể lên đến mức tối đa thực, đi từng hàng, vì vậy chúng tôi chỉ bắt đầu với một đầu vào đơn, sau đó có thể nhập vào, sau đó ba , v.v. Tại mỗi vị trí trong bảng, chỉ có hai khả năng cho giá trị tốt nhất: giá trị tốt nhất trước đó không sử dụng đầu vào hiện tại hoặc đầu vào hiện tại cộng với giá trị tốt nhất trước đó cho giá trị lớn nhất trừ đi đầu vào hiện tại (và từ đó chúng tôi tính giá trị bảng theo thứ tự, chúng tôi sẽ luôn có giá trị đó).

Chúng tôi cũng thường muốn theo dõi những mục nào thực sự được sử dụng để tạo kết quả. Để làm điều đó, chúng ta đặt Boolean cho một vị trí đã cho trong bảng thành true nếu và chỉ khi chúng ta tính giá trị cho vị trí đó trong bảng bằng cách sử dụng đầu vào mới cho hàng đó (thay vì chỉ sao chép giá trị tốt nhất của hàng trước đó). Kết quả tốt nhất là ở góc dưới cùng bên phải, vì vậy chúng tôi bắt đầu ở đó, và đi bộ lùi qua một hàng một lần tại một thời điểm. Khi chúng ta đến một hàng mà Boolean cho cột đó được đặt thành true, chúng ta biết chúng ta đã tìm thấy một đầu vào đã được sử dụng. Chúng tôi in ra mục đó, và sau đó trừ nó ra khỏi tổng số để lấy cột tiếp theo ở bên trái, nơi chúng ta sẽ tìm thấy đầu vào tiếp theo được sử dụng để tạo ra đầu ra này.

Đây là triển khai về mặt kỹ thuật trong C++, nhưng được viết chủ yếu theo kiểu C để làm cho mỗi bước càng rõ ràng càng tốt.

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

Có một vài điều bạn thường tối ưu hóa trong trường hợp này (mà tôi không vì mục đích dễ đọc).Đầu tiên, nếu bạn đạt đến số tiền tối ưu, bạn có thể ngừng tìm kiếm, vì vậy trong trường hợp này chúng tôi thực sự có thể thoát ra khỏi vòng lặp trước khi xem xét kết quả cuối cùng là 1 (kể từ 15 và 2 cho kết quả mong muốn là 17).

Thứ hai, trong bảng, chúng tôi chỉ thực sự sử dụng hai hàng tại một thời điểm nhất định: một hàng hiện tại và một hàng trước đó. Các hàng trước đó (trong bảng chính) không bao giờ được sử dụng nữa (ví dụ, để tính toán hàng [n], chúng tôi cần các giá trị từ row[n-1], nhưng không phải là row[n-2], row[n-3], ... row[0]. chỉ có hai hàng và chúng tôi trao đổi giữa hàng đầu tiên và hàng thứ 2. Một mẹo rất giống với C là chỉ sử dụng bit ít quan trọng nhất của số hàng, vì vậy bạn sẽ thay thế table[i] và table[i-1] bằng table[i&1] và table[(i-1)&1] tương ứng (nhưng chỉ cho bảng chính - không phải khi giải quyết các bảng used

Answer 2

Dưới đây là một ví dụ trong 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))] 

Ví dụ:

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

Ý tưởng đơn giản chỉ là để theo dõi những gì tiền có thể được thực hiện từ tất cả các yếu tố trước khi bạn đi qua mảng , cũng như một cách để thực hiện tổng số đó. Cuối cùng, bạn chỉ cần chọn gần nhất với những gì bạn muốn. Nó là một giải pháp lập trình động vì nó phá vỡ toàn bộ vấn đề thành các vấn đề phụ, và sử dụng một bảng để ghi nhớ các kết quả của các vấn đề phụ thay vì tính lại chúng.

Answer 3

ý tưởng Cato trong vợt:

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

.

Để có được một chương trình thậm chí terser, người ta có thể lấy terse-hash.rkt từ GitHub và viết:

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