[Chicago] The KnapSack problem.

[Joshua Herman]

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/f6414794/attachment.html>