Raul Miller wrote: > On 7/11/07, John Randall <[EMAIL PROTECTED]> wrote: >> Raul Miller wrote: >> > Background: http://xkcd.com/c287.html >> > (That's not really an np-complete problem, near as I can tell.) >> > >> It's an integer knapsack problem if you convert everything to cents. >>> Given a maximum weight W and n objects with integer weights, you can >>> solve >> this by dynamic programming in time O(nW). See >> >> http://cgm.cs.mcgill.ca/~msuder/courses/360/lectures/integer-knapsack.html > > Hmm... using the terminology of that page: > > [1] the weights of the problem were equal to their values > > [2] I'm not trying to maximize value, I'm trying to keep it from exceeding > a threshold. More precisely, I'm trying to find an exact threshold. > This is the same problem, isn't it? You are finding some combination of dishes that maximize the amount of money spent, subject to the constraint it does not exceed a certain value.
> [3] we are given an infinite set of objects to stuff in the knapsack, but > My first brute-force approach limited this to 49 objects > Oleg's approach limited this to 31 objects > My more long winded approach never concerns itself with the size of > this set How do you get an infinite number? > > But none of our solutions dealt with 2^n problems. My brute force > approach > considered 823543 cases (where 2^49 exceeds 5e14) and Oleg's > approach considered 14400 cases (where 2^31 exceeds 2e10). > The straight recursive version solves 2^n subproblems. When memoized it does it faster. This is the same as calculating the nth Fibonacci number: straight recursion is O(2^n), but the memoized version is O(n). > In other words, either I'm missing something about what makes these > problems NP complete, or the problem I'm tackling is not really an > NP complete problem. (Most likely both.) > The integer knapsack problem is in P. Best wishes, John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
