CODEWITHSUNDEEP
algorithmdynamic-programming
Monzy Zhang
Monzy Zhang

Reputation: 55

a dynamic program about subarray sum

I've see a problem about dynamic program like this:

let's say there is a array like this: [600, 500, 300, 220, 210] I want to find a sub array whose sum is the most closest to 1000 and bigger than it.(>=1000).

how can I write the code? I already understand the 01 backpack problem but still cannot make out this problem

Upvotes: 2

Views: 344

Answers (3)

webNeat
webNeat

Reputation: 2828

An approach to solve this problem can be done in two steps:

  • define a function which takes a subarray and gives you an evaluation or a score of this subarray so that you can actually compare subarrays and take the best. A function could be simply

    if(sum(subarray) < 1000) return INFINITY else return sum(subarray) - 1000

    note that you can also use dynamic programming to compute the sum of subarrays

  • Assuming that the length of your goal array is N, you will need to solve the problems of size 1 to N. If the array's length is 1 then obviously there is one possibility and it's the best. If size > 1 then we take the solution of the problem with length size - 1 and we compare it with every subarray containing the last element of the array and we take the best subarray as the solution of the problem with length size.

I hope my explanation makes sense

Upvotes: 0

olegarch
olegarch

Reputation: 3891

You can use transaction optimizer from the EmerCoin wallet. It exacly does, what you're looking for.

Upvotes: 0

Matt Jordan
Matt Jordan

Reputation: 2181

A few things:

First, I think you are referring to "dynamic programming", not "a dynamic program"; read up here if you want to know the difference: https://en.wikipedia.org/wiki/Dynamic_programming

Second, I think you mean "closest to 1000 but NOT bigger than it (< 1000)", since that is the general constraint. If you were allowed to go over 1000, then the problem doesn't make sense because there is no constraint.

Like the backpack problem, this is going to be a non-polynomial (NP) time problem (a problem where the time required to compute increases faster than polynomial growth - usually exponential or faster), where you would normally have to check every possible combination of numbers, which can take a long time for seemingly small set sizes.

I believe that the correct answer from the 5 you provided is 500+220+210, which sums to 930, the largest that you can make without going over 1000.

The basic idea of dynamic programming is to break the problem into smaller similar problems that are more easily computable; for example, if you had a million numbers and wanted to find the subset that is closest to 100000 but not over, you might divide the million into 100,000 subsets of 10 elements, and find the closest to a smaller number of each of those subsets, then use the resulting set of 100,000 sums to repeat with 10,000 sets, etc, until you reduce it to a close-but-not-perfect solution.

In any non-polynomial-time problem, dynamic programming can only be used in building a close approximation, since the solution isn't guaranteed to be optimal.

Upvotes: 1

Related Questions