CODEWITHSUNDEEP
c++algorithm
TNT_42
TNT_42

Reputation: 53

Knapsack with double data types

For all the Knapsack problem that I've seen so far on the internet, all of them have the form (cost, value) given a capacity of the cost variable. All of the problems seems to have cost as an integer only which makes it quite convenient to make a 2D array for Value and Keep array. But what if the cost variable isn't an integer but instead a double data type? There's no way to make a Value and Keep array based on the double data type. How can I approach this situation?

Ex:

budget: $3458

item_name(laptop) cost(1177.44) value (131)

item_name(desktop) cost(1054.44) value(35)

item_name(GPU) cost(1252.66) value(105)

item_name(CPU) cost(946.021) value(136)

Upvotes: 3

Views: 348

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65498

Switch to a dynamic program that finds the least costly solution for each value, with 2D arrays for Cost and Keep instead of Value and Keep. (The difference between the programs is minor.)

Upvotes: 1

comingstorm
comingstorm

Reputation: 26117

You can scan your input for the smallest exponent (using frexp()), and add in the mantissa precision (53 bits?) to find a scaling factor that will convert all your numbers to exactly proportionate integers.

You will need a bigint library to handle the resulting integers, though.

Upvotes: 1

Related Questions