tag:blogger.com,1999:blog-6314876008291942531.post2768879005148416741..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Given a set of integers select the minimum set with sum greater than kUnknownnoreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6314876008291942531.post-43011450123258356052011-09-29T01:06:21.620-07:002011-09-29T01:06:21.620-07:00assuming numbers = 1, 3, 4, 11 and want to find mi...assuming numbers = 1, 3, 4, 11 and want to find minimum set with sum > k = 14 you can perhaps use knapsack pseudo-polynomial solution on the negated numbers, e.g. <br />neg.numbers = -1, -3, -4, -11 and find the knapsack solution with limit k=-15 - this is likely to give -15 = with the numbers -4, -11.<br />Dynamic programming pseudo solution has complexity O(NW), but looks like there has been recent work (2010) on improving it:<br />http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5564469Anonymoushttps://www.blogger.com/profile/12610829647945619039noreply@blogger.com