How to select weighted items to maximize profit?

This might sound like a simple problem but I am not able to get a good solution. The problem is similar to a knapsack problem but slightly modified.

I have a bag which has a fixed capacity, say C. We have a list of items and their weights. The total weight of all the items is greater than C. How can I fit the maximum number of items in the bag (Also trying to best fill the bag) ?

I thought of sorting the list and select items until the bag is fully filled but the below example disproves the idea

C = 100 and L = 50, 40, 20, 30.

When I sort I get 20, 30, 40, 50 hence my allocation will be (20+30+40) = 90. But we can get a better combination (20+30+50) = 100.

The problem can be solved by transforming this problem into knapsack by giving the weights for each item equivalent to its weight. Is there any other algorithm ?

DISCLAIMER: This is not the most efficient solution; however, this is a solution.

I would -

• Generate all possible sums
• Filter sums by max capacity (bagSize)
• Get the max sum from the generated sums
• Filter sums by the max sum
• Find and filter by the maximum number of items left

Here's an example in everyone's favorite language - Haskell!

import Data.List

knappsack bagSize items = answers
  where
    sums = [(xs, sum xs) | xs <- subsequences items]
    sumFilter = filter ((<= bagSize) . snd) sums
    maxSum = foldl max 0 . map (sum . fst) $ sumFilter
    maxFilter = filter ((== maxSum) . snd) sumFilter
    maxLen = foldl max 0 . map (length . fst) $ maxFilter
    lenFilter = filter ((== maxLen) . length . fst) maxFilter
    answers = lenFilter