0/1 Knapsack with irrational weights

Posted by user356106 on Stack Overflow See other posts from Stack Overflow or by user356106
Published on 2010-06-03T04:52:08Z Indexed on 2010/06/03 4:54 UTC
Read the original article Hit count: 220

Filed under:

data-structures

|

algorithm-design

Consider the 0/1 knapsack problem. The standard Dynamic Programming algorithm applies only when the capacity as well as the weights to fill the knapsack with are integers/ rational numbers. What do you do when the capacity/weights are irrational?

The issue is that we can't memoize like we do for integer weights because we may need potentially infinite decimal places for irrational weights - leading to an infinitely large number of columns for the Dynamic Programming Table .

Is there any standard method for solving this? Any comments on the complexity of this problem? Any heuristics?

What about associated recurrences like (for example):
f(x)=1, for x< sqrt(2)

f(x)=f(x-sqrt(2))+sqrt(3)

© Stack Overflow or respective owner

Related posts about data-structures

Clever ways of implementing different data structures in C & data structures that should be used mor

as seen on Stack Overflow - Search for 'Stack Overflow'
What are some clever (not ordinary) ways of implementing data structures in C, and what are some data structures that should be used more often? For example, what is the most effective way (generating minimal overhead) to implement a directed and cyclic graph with weighted edges in C? I know that… >>> More
Is there a way to track data structure dependencies from the database, through the tiers, all the way out to a web page?

as seen on Programmers - Search for 'Programmers'
When we design applications, we generally end up with the same tiered sets of data structures: A persistent data structure that is described using DDL and implemented as RDBMS tables and columns. A set of domain objects that consist primarily of data structures, usually combined with business-rule… >>> More
Why are data structures so important in interviews?

as seen on Programmers - Search for 'Programmers'
I am a newbie into the corporate world recently graduated in computers. I am a java/groovy developer. I am a quick learner and I can learn new frameworks, APIs or even programming languages within considerably short amount of time. Albeit that, I must confess that I was not so strong in data structures… >>> More
Thread-safe data structures

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have to design a data structure that is to be used in a multi-threaded environment. The basic API is simple: insert element, remove element, retrieve element, check that element exists. The structure's implementation uses implicit locking to guarantee the atomicity of a single API call.… >>> More
Data Structures

as seen on Stack Overflow - Search for 'Stack Overflow'
There is a large stream of numbers coming in such as 5 6 7 2 3 1 2 3 .. What kind of data structure is suitable for this problem given the constraints that elements must be inserted in descending order and duplicates should be eliminated. I am not looking for any code just ideas? I was thinking… >>> More

Related posts about algorithm-design

Solutions for exercises in The Algorithm Design Manual

as seen on Stack Overflow - Search for 'Stack Overflow'
Does anybody know where to find solutions for the exercises in the book The Algorithm Design Manual? >>> More
Algorithm design, "randomising" timetable schedule in Python although open to other languages.

as seen on Stack Overflow - Search for 'Stack Overflow'
Before I start I should add I am a musician and not a native programmer, this was undertook to make my life easier. Here is the situation, at work I'm given a new csv file each which contains a list of sound files, their length, and the minimum total amount of time they must be played. I create… >>> More
Algorithm for dynamic combinations

as seen on Stack Overflow - Search for 'Stack Overflow'
My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to… >>> More
Disk Search / Sort Algorithm

as seen on Stack Overflow - Search for 'Stack Overflow'
Given a Range of numbers say 1 to 10,000, Input is in random order. Constraint: At any point only 1000 numbers can be loaded to memory. Assumption: Assuming unique numbers. I propose the following efficient , "When-Required-sort Algorithm". We write the numbers into files which are designated… >>> More
Dynamic programming practice problems with solutions

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is there a website or book that contains practice problems and solutions? Thanks Bala >>> More