0

I'm looking for an algorithm to solve the follwoing problem (I will explain it with an example):

Let say I have 10.000 $ available amount and following costs I can finance using my amount:

cost 1: 1.000 $

cost 2: 3.000 $

cost 3: 4.000 $

cost 4: 5.000 $

The costs cannot be paid partially so either you pay the whole cost or you don't pay it at all. What I am looking for is an algorithm which helps me find the combination of costs which will not exceed available amount, but on the other side use the most part or the whole available amount.

In my example it would be: cost 1 + cost 3 + cost 4.

I would like also to add an parameter which determines how many costs can be maximally financed. If I say in my example that only two costs can be payed, cost 3 and cost 4 will be returned.

My approach would be to check all available combinations, sum them and pick the one which best uses the available amount. I wonder however if there is a simpliest way to find the optimal combination.

Okizb
  • 99
  • 1
  • 15
  • 12
    This sounds like a variant of the [knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem). – Oliver Charlesworth Jul 29 '13 at 12:26
  • 1
    Seems to be a duplicate of http://stackoverflow.com/questions/16022205/how-do-i-find-the-closest-possible-sum-of-an-arrays-elements-to-a-particular-va/16023064#16023064 – Vincent van der Weele Jul 29 '13 at 12:43
  • @Oli Charlesworth: thank you for letting me know how this problem is called and for the provided link. Because I have always only a few costs the best way to find an optimal solution will be my original approach to go through all possible combinations and picking the best one (as also Mecki suggests). – Okizb Jul 29 '13 at 13:12

5 Answers5

1

This is a simple dynamic programming problem (A variation of Knapsack). State can be defined as [position][rest_amount][how_many_bills_can_be_paid]. A recursive solution below:

assuming Cis the array of cost and memo is initialized with -1:

const int N = 10;    //number of notes to pay
int memo[N][M][K];   //remember to initialize it with -1

int func(int cur_index,int rest_amount,int K){

    if(cur_index == N){
        return 0;
    }

    int &ret = memo[cur_index][rest_amount][K];
    if(ret != -1) return ret;    //memoization ensures we won't solve the same sub problem more than once
    ret = 0;
    if(rest_amount >= C[cur_index]  && K > 0 )
    ret = func(cur_index+1,cost+C[cur_index],K-1);

    ret = max(ret,func(cur_index+1,cost,K);

    return ret;
}
Fallen
  • 4,435
  • 2
  • 26
  • 46
  • I'm afraid I cannot understand your answer completely. Is it possible to "translate" it into PHP or java, maybe using my example as variables in your example? I would be very grateful for that. – Okizb Jul 29 '13 at 15:58
  • @Okizb C is pretty similiar to java but diifferences in the example is he declare array using `int memo[N][M][K];` instead `int[N][M][K] memo;` in java and `int func(int cur_index,int rest_amount,int K)` is `public int func(int cur_index,int rest_amount,int K)` in java – Blanket Fox Apr 22 '21 at 04:41
0

You can sort the list and pick the top until your budget is depleted. It's also used in bin-packing and it's guarantee to be within some range of the optimum.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • 1
    It won't find optimal value: lets say total amount is 10k and costs are 6k, 5k, 5k. Your soultion will choose 6k instead of 5k+5k. – Ari Jul 29 '13 at 12:31
  • @Ari as Phpdna says, it's an approximation algorithm (from your example I would say it is a 2-approximation). However, dynamic programming can easily get you the optimal solution indeed. – Vincent van der Weele Jul 29 '13 at 12:40
  • I didn't say it's optimal I wrote it's within optimality. The search space is to big. The problem is also np hard. – Micromega Jul 29 '13 at 12:41
0

I can't improve your solution for general data, however there are few improvements which can speed it up.

If total amount N is quite low there is simple dynamic solution:

setOfValues
put totalAmount to setOfValues
foreach cost do
    foreach amount in setOfValues do
        if (amount - cost) > 0 and not exists (amount - cost) in setOfValues
            put (amount - cost) to setOfValues
get lowest setOfValues

You can simple upgrade it to additional requirements (like up to x costs).

Ari
  • 3,101
  • 2
  • 27
  • 49
  • Can you explain this a bit more? – Micromega Jul 29 '13 at 12:46
  • @Phpdna this is a similar algorithm as I gave [a while ago](http://stackoverflow.com/a/16023064/2095090) to another question, but in a more obscure language. I think it's easier to follow there. – Vincent van der Weele Jul 29 '13 at 12:58
  • How much is the search space smaller? I have problems to understand it. – Micromega Jul 29 '13 at 13:03
  • @Phpdna Example: If there is amount 1000000 and 100 different costs my algorithm will do about 100kk operations instead of 2^100 (brutal algorithm) and find optimal solution. – Ari Jul 29 '13 at 13:10
  • Your algorithm find the optimum in 100000 iteration? How much in percentage is the search space smaller? – Micromega Jul 29 '13 at 13:14
  • @phpdna For this example it is 10^5 in compare to ~10^30 so it is 10^25 times faster. Of course there is data for which my algorithm would be slower. But I think it will behave better in general and its easy to check data to choose better algorithm. – Ari Jul 29 '13 at 19:32
  • @heuster: I've read your example but when you have best solution in sums set it doesn't give you give you the correct combination? – Micromega Jul 29 '13 at 19:53
  • @Phpdna that is correct. However, it is always possible to keep a witness of the optimal solution, without effecting the asymptotic running time. – Vincent van der Weele Jul 30 '13 at 07:07
  • @heuster: in your example it needs 3 iteration. all permutations is 3! how do you calculate the cut? why is there an upper bound? – Micromega Jul 30 '13 at 11:03
  • @heuster:http://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete/17958172#17958172 – Micromega Jul 30 '13 at 23:26
0

I designed an algorithm like this in java some weeks ago. I used a binary matrix with width N, where N is the number of different costs, and the height will be 2^N, giving us all possible combinations.

So the first item would refer to the lowest cost in your case. Here is an example with 1000, 3000, 4000. (You can expand this, but I just want to show you how I did.)

Width = N = 3

Height = 2^N = 8

0 0 0 = 0       +   0       +   0       =   0
1 0 0 = 1000    +   0       +   0       =   1000
0 1 0 = 0       +   3000    +   0       =   3000
1 1 0 = 1000    +   3000    +   0       =   4000
0 0 1 = 0       +   0       +   4000    =   4000
1 0 1 = 1000    +   0       +   4000    =   5000
0 1 1 = 0       +   3000    +   4000    =   7000
1 1 1 = 1000    +   3000    +   4000    =   8000

I had a list with the costs in it. And as i went down the matrix row by row, i just checked the list where there was a 1 on the matrix. Since the costs are sorted, the row i find that is equal or greater than the total amount will be the lowest possible.

Tell me if you don't understand and i'll elaborate!

Goatcat
  • 1,133
  • 2
  • 14
  • 31
0

Your problem is a NP problem; there is no known solution to this problem that will guarantee to find an optimal solution within an acceptable time frame. The only way to really find an optimal solution would be to try all possible solutions and then check which one is optimal. If you have thousands of costs, though, this would be awfully slow, of course.

All other solutions that are faster than the naive approach mentioned above, are not guaranteed to find an optimal solution. They may find a good solution, yet you can never say for sure if a better solution was possible or not.

It is the same problem as the following: You have a truck that can transport X pounds of goods and you have goods of different weights. Your goal is to make optimal use of the available capacity. This one is also known as the "knapsack problem". There are no better solutions known other than those listed on this page. None of them can guarantee an optimal result, though.

Mecki
  • 125,244
  • 33
  • 244
  • 253
  • These claims are a little too strong. The knapsack problem is *weakly* NP-hard, which means it has a polynomial solution in `n` (the number of items) and the *value* of `X` (the target value). For typical applications, dynamic programming is *much more* efficient than brute forcing. – Vincent van der Weele Jul 29 '13 at 14:10
  • Recently I tested a dynamic solution for the tsp problem and it's impressive but I 'my still wondering how it works. Also it needs a lot more memory which can also become a big problem. – Micromega Jul 29 '13 at 14:35
  • @Heuster Even the dynamic programming solution can be exponential time, since it is no polynomial solution, it is a *pseudo-polynomial solution*. That means if your budget increases a lot and the number of costs increases a lot, the complexity grows much faster than would be the case for a real polynomial solution. The dynamic solution can easily get awfully slow, it is only fast as long as the input values stay small enough. – Mecki Jul 29 '13 at 14:54
  • @Mecki absolutely, I agree on that. And clever pruning can make the brute force approach really efficient. I'm just saying that "every solution that is faster than brute force, is not guaranteed to give an optimal solution" is little strong. :) – Vincent van der Weele Jul 29 '13 at 15:16