knapsack problem?

This is a discussion on knapsack problem? within the General Discussions forums, part of the Community Boards category; If i want to find three distinct int a,b,and c such that there are submitted to the constraint a+b+c=1000, is ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460

    knapsack problem?

    If i want to find three distinct int a,b,and c such that there are submitted to the constraint a+b+c=1000, is this a problem for the knapsack algo? I thought of doing this the bruteforce way, but that would be foolish 'cuz there are way too many combination of 3 numbers below 1000.
    Last edited by nimitzhunter; 01-27-2011 at 09:50 PM.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by nimitzhunter View Post
    If i want to find three distinct int a,b,and c such that there are submitted to the constraint a+b+c=1000, is this a problem for the knapsack algo? I thought of doing this the bruteforce way, but that would be foolish 'cuz there are way too many combination of 3 numbers below 1000.
    Not really. The knapsack problem would be if you had a bunch of numbers and had to pick the one set of three out of them that added up to 100. If you have a free choice, then you just pick a and b and set c = 100-a-b.

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Tabstop, you mean that if there are many solution exists, then the knapsack problem would allow me to pick the optimal one? It seems like I am left with bruteforcing the way out of this. Thanks for your replay, tabstop.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by nimitzhunter View Post
    Tabstop, you mean that if there are many solution exists, then the knapsack problem would allow me to pick the optimal one? It seems like I am left with bruteforcing the way out of this. Thanks for your replay, tabstop.
    I think you lack something in your problem description. There are many solutions to a+b+c=1000, and they're all extremely easy to find, but you didn't say anything about one solution being better than the others.
    You mean that a, b and c are part of a set? Like, given the subset of numbers, find 3 numbers for which a+b+c=1000? If so; I don't think that's NP complete. But then again, then what does your solution have to do with brute forcing 1000 numbers?

    Brute forcing 1000 items isn't a lot by the way. Nor is 1,000,000. Usually brute forcing 10M takes about one second, depending of course on the processor and difficulty on the algorithm, but that's the rule I used for myself in programming contests. Usually brute force was fine for les than 10M items.

    But as I said, if your problem is to select three items from a set so that a+b+c=1000, I'm quite sure that's not NP complete, but I'm not going to take the time to share the algorithm if I'm not sure that is indeed the problem. Also, I'm not sure my algorithm would even work, didn't think enough about it yet.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by nimitzhunter View Post
    Tabstop, you mean that if there are many solution exists, then the knapsack problem would allow me to pick the optimal one? It seems like I am left with bruteforcing the way out of this. Thanks for your replay, tabstop.
    Not even a little bit. The knapsack problem is this: you have items weighing 1, 4, 7, 11, 13, 19, 23, 29, 35, 41, 49, 53, 57, 65, 72, 76, 79, and 85 pounds. You can get 100 pounds of stuff in your knapsack. Pick numbers but only numbers out of the list that add up to 100.

    The problem as you originally described it is a (pair of) for loop(s), and therefore isn't nearly grand enough to have a name.

  6. #6
    Registered User \007's Avatar
    Join Date
    Dec 2010
    Posts
    179
    Do these items have to add up to exactly 100, 1000 etc? Can we make a best fit? Is the list sorted from highest to lowest or vise versa?

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,575
    See the knapsack problem description on wikipedia. You are confusion things, since this problem requires a value pair of items in which one value determines the "value" and the other the "weight", for what is called a single constrain problem. There's nothing lower than that.

    What you have on your problem is a single value, not a pair of values. As tabstop mentioned all you need is a couple of for loops to solve it.


    >> Do these items have to add up to exactly 100, 1000 etc?

    No. Their weight must be as high as possible up until a limit, while their value must be as high as possible.

    >> Can we make a best fit?

    That's exactly what you want to achieve.

    >> Is the list sorted from highest to lowest or vise versa?

    Usually there's only one possible solution. Multiple solutions in which the same value is achieved is most probably a weakness on the problem description.
    Last edited by Mario F.; 01-28-2011 at 10:03 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    460
    Quote Originally Posted by tabstop View Post
    Not even a little bit. The knapsack problem is this: you have items weighing 1, 4, 7, 11, 13, 19, 23, 29, 35, 41, 49, 53, 57, 65, 72, 76, 79, and 85 pounds. You can get 100 pounds of stuff in your knapsack. Pick numbers but only numbers out of the list that add up to 100.

    The problem as you originally described it is a (pair of) for loop(s), and therefore isn't nearly grand enough to have a name.
    Yeah, I made the problem harder than it should be.
    "All that we see or seem
    Is but a dream within a dream." - Poe

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  3. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  4. Knapsack Problem
    By Fork in forum C Programming
    Replies: 4
    Last Post: 11-13-2006, 12:42 PM
  5. Multiple Knapsack Problem
    By polymeta in forum C Programming
    Replies: 3
    Last Post: 11-15-2001, 08:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21