knapsack problem ?

This is a discussion on knapsack problem ? within the C Programming forums, part of the General Programming Boards category; The knapsack problem is as follows: given a set of integers S = {s1 , s2 , . . . ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    5

    Question knapsack problem ?

    The knapsack problem is as follows: given a set of integers S = {s1 , s2 , . . . , sn },
    and a target number T , find a subset of S which adds up exactly to T . For example,
    there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not
    T = 23.
    Find counterexamples to each of the following algorithms for the knapsack problem.
    That is, giving an S and T such that the subset is selected using the algorithm does
    not leave the knapsack completely full, even though such a solution exists.


    (a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the
    first-fit algorithm.
    (b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit
    algorithm.
    (c) Put the elements of S in the knapsack from largest to smallest.

  2. #2
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    398
    Give it an attempt, and we can help you if you run into any problems.

    Please see the homework policy:
    C Board - Announcements in Forum : General Programming Boards

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