Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C# Algorithms
Hi everybody!
I need some help solving an algorithm in C#.
The knapsack algorithm (also called Rucksack algorithm) is a problem in which
a rucksack has to be packed with a certain weight W using only a certain number of items N that can be choosen from a list of items S.
For simplification the list S only contains the weights of the items.
 
The values are:
 
   W = 15
   N = 17
   S = [1, 2, 4, 9]
 
I need help in how to go about solving this problem in C#.
 
Thanks in advance!
Posted 24-Dec-10 3:24am
Edited 24-Dec-10 3:41am
v2
Comments
Manfred R. Bihy at 24-Dec-10 9:32am
   
And I want a bit more explanation, please. From what you wrote I'm pretty sure you're talking about the famous Rucksack or Knapsack algorithm, but it would serve you well if you did a little bit more explaining.
Just plainly stating that you want a prefabricated solution from us without any sign of engagement from you, there isn't much hope for you that anybody will help at all.
If you need help re-formulating the question you can aslo ask for that, and more likely than not somebody will do just that.
Manfred R. Bihy at 24-Dec-10 9:43am
   
I was feeling a bit christmassy, so I just reformulated your question a bit :).
Smithers-Jones at 24-Dec-10 9:44am
   
Manfred, you are too good. Rewriting this guys one-line demanding "question"... Cheers.
Smithers-Jones at 24-Dec-10 9:28am
   
Wow, how demanding and rude. You know, just because it's Christmas, that doesn't mean, people are giving code away for free. Either show some effort and come back, when you are stuck and need real help, or pay for it.
 
modified: The OP's original question was a rude and demanding one-liner, thus my comment.
Manfred R. Bihy at 24-Dec-10 9:49am
   
@Smithers: Well looking at the other question he posted, I didn't even get it right. :-D
No wonder as there was not much to go on anyhow, Cheers!
Happy Xmas, solstice or whatever you're celebrating this time of the year :)
SAKryukov at 24-Dec-10 17:05pm
   
Smithers-Jones: sorry, what was so rude in this question? I can see many other inquirers are really rude (as a rule, more ignorant person is more rude), but this one is not too bad. However, I agree that an inquirer needs to do maximum effort first to make a question attractive and worthy.
Manfred R. Bihy at 24-Dec-10 17:25pm
   
SAKryukov: When you click on the link "Revision" below the question you can review older versions of the question including the original post. If you look at the version of the question OP had posted you'd probably understand Smithers-Jones first comment. :)
digital man at 24-Dec-10 10:41am
   
No homework questions! Besides, there is a wealth of information if you could be bothered to try Googling...
SAKryukov at 24-Dec-10 23:50pm
   
Or, I see, thank you... Well, it was kind of impolite. To me, just a sloppy wording, punctuation, lack of proper casing, hard-to-read formatting -- all is quite impolite. But again, some inquirers are worse. In this case, you read this bad question and just choose to ignore...
 
One example, just for fun. Recently, there was a discussion of one other inquirer behavior, pretty much like this one (but, to me, more of the inquirer's fault). In next question, the inquirer requested: "Please don't post irrelevant comments" -- as if not paying enough attention for good answers, asking same question again several times and failure to work and learn would be less of distraction...
 
I like people who work hard to learn something good too much. Lazy and ignorant people effectively steal from them even more than from us answering questions.
 
Best wished in New Year to everyone!
Sandeep Mewara at 24-Dec-10 10:56am
   
No effort.
Marcus Kramer at 24-Dec-10 11:38am
   
@Smithers-Jones: Reading your first post(which I agree with, BTW), I couldn't help but have a good laugh. If you put in the appropriate pause at all your commas when reading the answer, I could swear I could hear James T. Kirk's voice...

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

Ok, this is a funny problem.
 
In first place, I suspected this could be a NP-complete problem but later I suspected I was mistaken because some "backdoor" algorithm might exist. However, this article on the problem states that it is indeed a NP-complete one. But only when I learned from the same article that there are different Knapsack and Knapsack-like problems, only then I paid closer attention to the formulation of the present Question. Silly me!
 
Well, this is neither basic nor generalized Knapsack problem, so let's consider this is a Knapsack-like problem, rather simplified. The formulation is contradictory: the words "I need some help solving an algorithm in C#" hint that general algorithm is required, but is this case, why giving the following constraints: W = 15, N = 17, S = [1, 2, 4, 9]? With this figures, formally speaking, algorithm is not required, proven solution would be the answer.
 
As my mood of relaxing after the Christmas Eve party does not inspire much enthusiasm for working at the general algorithm, let' first think about the formal solution with constraints.
 
Ok, we can immediately see that there is no solution.
The proof: as minimum S=1, minimum sum of N weights is equal to N*1 = N = 17, which is more than W = 15. Now, follow the most delicate and hard-to-understand inference: if minimum sum of N weights is less then W, any other combination of N weights is more than W => no combination of N weights is equal to W => Thumbs Down | :thumbsdown: ---- Wink | ;)
 
Aha, now we can see that the inquirer is locked in the corner. I do understand that shaden2009 could have done a simple mistake; and the figures could be different. Who knows? Slip of a hand. May be W and N should be swapped; then the problem is solvable... -- too late! The proof is presented, and shaden2009 assumed sole responsibility for the formulation of the problem.
 
In this way, shaden2009, being a undoubtedly, honest person (we all are supposed to be honest aren't we?) has nothing to do but accept my answer now.
 
If there is more accurate formulation of the problem which would make it more sensible, we would certainly enjoy considering it (shall we?), but that should be another question. The present answer should be accepted; and the present question closed.
 
Thank you for attention!
Take it easy! Wink | ;)
Best wishes in New Year, everyone!
  Permalink  
Comments
Sandeep Mewara at 25-Dec-10 1:41am
   
Now, since you have replied this with something really relevant and given OP an exception for this time... I will delete my answer.
 
BTW, good work. A 5! again...
Espen Harlinn at 26-Feb-11 11:22am
   
Very good reply - my 5

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 620
1 Maciej Los 610
2 CPallini 255
3 RyanDev 161
4 Peter Leow 125
0 OriginalGriff 5,784
1 Sergey Alexandrovich Kryukov 4,838
2 Peter Leow 3,009
3 Maciej Los 2,894
4 DamithSL 2,465


Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 25 Dec 2010
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100