-2

Question:

Given an array of floats (size N < 100), find the subset (size M = 10) whose sum is maximal but less than value K.

Example (using ints for simplicity)

INPUT:

array = [1,2,3,4,5,6,7,8,9,10,11,12,13]
K = 60

OUTPUT:

subset = [1,2,3,4,5,6,7,8,10,13] # sum of 59

I've tried searching on G4G, but I haven't found anything that accounts for the subset size of M = 10. I'm trying to solve this with Python 3, but any references or sources would be much appreciated.

Andrew Shi
  • 7
  • 2
  • 1
    Is this homework assignment? Seems to be subset_sum variants. – Daniel Hao Jan 01 '21 at 13:31
  • @DanielHao no, for a personal project. – Andrew Shi Jan 01 '21 at 13:33
  • @DanielHao the problem is I don't know where to start. I googled, and trust me, I couldn't find anything regarding the fixed subset size m = 10. – Andrew Shi Jan 01 '21 at 13:36
  • What have you tried so far? SO exists to help when you encounter issues with your code, not to straight up write it for you. That being said, this can easily be implemented with a greedy search algo. – CerebralFart Jan 01 '21 at 13:51

1 Answers1

2

A good starting point would be to read up on the 0-1 knapsack problem: Given a set of items with corresponding values and weights, and a maximum weight allowance W, find the set of items of maximum value which is within the weight allowance W.

Your problem is the same as this problem, but with all the item values = their weights - so you can just use a solution to the knapsack problem, or maybe (probably) you can make something a bit more time-efficient exploiting this.

Good luck!

devck
  • 331
  • 2
  • 8