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.
[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
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).
And, my long winded approach considers only a tiny fraction of that. If
I change 'order' so it reports the shape of pos inside the loop (after it
has been reassigned), I get:
15.05 order ap
1 6
2 21
3 47
4 38
5 9
6 1
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.)
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
