[Chicago] The KnapSack problem.

[Joshua Herman]

All,
The n is supposed to be an exponential apparently the cut and paste didn't
preserve its formatting.
so it is O(1.32113)^n

On Sat, Aug 8, 2015 at 5:28 AM, Joshua Herman <zitterbewegung at gmail.com>
wrote:

> Dear Lewellit,
> The KNAPSACK problem is NP-complete as a decision problem and NP-hard as a
> optimization problem.
> Linear programming is NP-hard and I believe from the complexity zoo that
> it also is a member of the complexity class FP.
>
> I believe if you take your KNAPSCAK problem and you reduce it to a SAT
> solve the runtime would be much better. It would be
> O(1.32113n)
> with a sat solver that you can use below
> http://cstheory.stackexchange.com/a/1070/5385
>
> Sincerely,
> Joshua Herman
>
> On Sat, Aug 8, 2015 at 1:35 AM, Lewit, Douglas <d-lewit at neiu.edu> wrote:
>
>> Hi guys,
>>
>> Here's my brute-force solution to the knapsack problem.  I like it!  The
>> running time I think is O(2**n) where n is the number of items, so if you
>> plan to stuff like 30 or more items in your knapsack then my algorithm may
>> not provide a very fast, efficient approach!  But for smaller problems the
>> running time should not be that bad.
>>
>> I know somebody on the list wrote, "For the love of other developers,
>> please use 4 spaces!"  Well, I wish I could be accommodating, but.... I'm
>> not a big fan of just 4 spaces!!!  I gotta have 6 spaces at least.  Don't
>> know why!  Maybe there's something wrong with my eyes, right?
>>
>> This was actually a problem on my Algorithms final at Northeastern.  (But
>> we had to write our code in Java, and we couldn't test it on a computer.
>> Just our best handwritten approximation of the correct code.)
>>
>> Just sharing this with everyone on the list.  I hope the feedback is
>> good!  If not, well.... you can't complain about the price cause it's
>> FREE!!!  LOL!!!
>>
>> By the way, on a totally different subject here, have you noticed that a
>> lot of CS professors think that all their students are plagiarists,
>> downloading all their program files from Github and StackOverflow?  I gotta
>> say that this attitude is really offensive to me because I don't steal
>> other people's programs.  I write my own!  I've got a couple friends in
>> other states with PhD's (both in mathematics) and I have heard plenty of
>> stories about professors guilty of plagiarism, stealing work from graduate
>> students and research assistants and then taking all the credit for it.  I
>> heard a similar story from a guy who was a graduate history major at DePaul
>> a long time ago.  He told me that some academics that he worked with at
>> DePaul were absolutely ruthless, and thought it was perfectly okay to take
>> credit for the work of graduate students and research assistants!  I just
>> get tired of professors who imply that their students are all a big bunch
>> of thieves and plagiarists.  I'm sure it happens, but I doubt if it happens
>> with any great regularity.  What do you think?
>>
>> By the way, I'm pretty sure that the famous KNAPSACK PROBLEM is really a
>> special type of linear programming problem that has integer constraints.
>> Linear programming is definitely pretty interesting, but some of the
>> algorithms can get kind of rough and intimidating.  But I have heard that
>> the algorithms of linear programming and operations research in general are
>> extremely important in business and economics.
>>
>> Have a fun and fabulous weekend!
>>
>> Kind regards,
>>
>> Douglas Lewit
>>
>>
>> _______________________________________________
>> Chicago mailing list
>> Chicago at python.org
>> https://mail.python.org/mailman/listinfo/chicago
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150808/14d1dd26/attachment.html>