Knapsack with continuous (non distinct) constraint

Question

I watched Dynamic Programming - Kapsack Problem (YouTube). However, I am solving a slightly different problem where the constraint is the budget, price, in double, not integer. So I am wondering how can I modify that? Double is "continuous" unlike integer where I can have 1,2,3 .... I don't suppose I do 0.0, 0.1, 0.2 ...?

UPDATE 1

I thought of converting double to int by multiply by 100. Money is only 2 decimal places. But that will mean the range of values will be very large?

UPDATE 2

The problem I need to solve is:

Items have a price (double) & satisfaction (integer) value. I have a budget as a constraint and I need to maximize satisfaction value.

In the youtube video, the author created two 2d array like int[numItems][possibleCapacity(weight)]. Here, I can't as budget is a double not integer

Answer 1

You will have to do what you said in UPDATE 1: express the budget and item prices in cents (assuming we are talking about dollars). Then we're not talking about arbitrary precision or continuous numbers. Every price (and the budget) will be an integer, it's just that that integer will represent cents.

To make things easier let's assume the budget is $10. The problem is that the Knapsack Capacity will have to take all the values in:

[0.00, 0.01, 0.02, 0.03, ..., 9.99, 10.00] 

The values are two many. Each line of the SOLUTION MATRIX and the KEEP MATRIX will have 1001 columns so you won't be able to solve the problem by hand (if the budget is millions of dollars even a computer might have a hard time) but that is inherent to the original problem (you can't do anything about it).

Your best bet is to use some existing code about KNAPSACK or maybe write your own (I don't advice that).

If you can't find existing code about KNAPSACK and are familiar with Linux/Mac I suggest you install the GNU Linear Programming Kit (GLPK) and express the problem as an Integer Linear Program or a Binary Linear Program (if you're trying to solve the 0-1 Knapsack). It will solve the problem for you (plus you can use it through C, C++, Python and maybe Java if you need to). For help using GLPK check this awesome article (you'll probably need part 2, where it talks about integer variables). If you need more help with GLPK please leave a comment.

EDIT:

Basically, what I'm trying to say is that your constraint is not continuous, it's discrete (cents), your problem is that the budget might be too many cents so you won't be able to solve it by hand.

Don't get intimidated because your budget might be several dollars -> several hundreds of cents. If your budget is just 18 cents your problem's size will be comparable to the one in the YouTube video. The guy in the video wouldn't be able to solve his problem either (by hand) if his knapsack size was 1800 (or even 180).

Answer 2

If you want to use floating point numbers with arbitrary precision (i.e., don't have a fixed number of decimals), and these are not fractions, dynamic programming won't work.

The basis of dynamic programming is to store previous results of a calculation for specific inputs. Therefore, if you used floating point numbers with arbitrary precision, you would need practically infinite memory for each of the possible floating point numbers and, of course, do infinite calculations, something that is impossible and non-optimal.

However, if these numbers have a fixed precision (as with the money, which only have two decimal numbers), you can convert these into integers by multiplying them (as you've mentioned), and then solve the knapsack problem as usual.