Optimizing Loading Problem

[Morning]

we have n numbers in a set A
A = {a1, a2, a3 ... an}

and a number s.

I want to pick up some numbers from A, and sum of these numbers will equals to s or closest to s(but smaller than s).

input:
3
1 2 7
9

output:
2 7


input:
3
1 2 7
5

output
1 2

Can I solve this problem using dynamic programming?
Thanks:)

[ayon]

Code: Select all

DP[n][s] = s, if n = 0
             = DP[n-1][s], if a[n] > s
             = min(DP[n-1][s-a[n]], DP[n-1][s]), otherwise

this may work for nonnegative integers