Buy the most appropriate items

Question

A store is having a big sale.
If your price reaches $199 or more, you can reduce it by $100.
You can buy each product only once.
Here's an example list of products: (in order to simplify, the names of the products are represented by letters)

+------+-------+
| name | price |
+------+-------+
| A    | 26.9  |
| B    | 24.9  |
| C    | 49.9  |
| D    | 28.9  |
| E    | 14.9  |
| F    | 16.9  |
| G    | 19.9  |
| H    | 19    |
| I    | 14.9  |
| J    | 14.9  |
| K    | 26.9  |
+------+-------+

Input

• A list of product price, such as the above example.
• N the item list size 10 <= N <= 100
• X a price

Output

The best shopping strategy to save money. Find out the least expensive purchase list with a total price of more than X, and output:

• The most appropriate total price (before deduction), for the data above, X = $199, and the most appropriate total price is 199.2

Notes

• Your code can be a function (method) or a full working program.
• Make your algorithm as fast as possible (less time complexity)!
• If codes have the same time complexity, the one which uses less space wins.

Answer 1

Python 2, \$O(2^{n/2})\$

import sys
def subsetsum(nums, target):
#    totalsum = sum(nums)
#    if(totalsum == target):
#        return target
#    if(totalsum < target):
#        return -1

    sumsA = {}
    sumsB = {}
    for n in nums[::2]:
        for k,v in sumsA.items() + [(0,[])]:
            newsum = k + n
            if newsum not in sumsA:
                sumsA[newsum] = v + [n]
                if newsum == target:
                    print "target found in sumsA loop: "
                    return target
    minsum = sys.maxsize
    for n in nums[1::2]:
        for k,v in sumsB.items() + [(0,[])]:
            newsum = k + n
            if newsum not in sumsB:
                sumsB[newsum] = v + [n]
                if newsum == target:
                    print "target found in sumsB loop: "
                    return target
                for a in sumsA:
                    combsum = a + newsum
                    if combsum == target:
                        print "target found in combined sumsA and sumsB loop: "
                        return target
                    if combsum > target and combsum < minsum:
                        minsum = combsum
    print "target",target,"not found, so return the closest alternative: "
    return minsum

# Test cases:
print subsetsum([26.9, 24.9, 49.9, 28.9, 14.9, 16.9, 19.9, 19, 14.9, 14.9, 26.9], 199)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
                 21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
                 21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
                 40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
                 49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 1000)
print subsetsum([47.5, 1.0, 19.6, 16.7, 21.8, 5.6, 40.4, 31.8, 25.4, 21.9,
                 21.7, 17.6, 48.4, 17.4, 41.1, 8.9, 12.2, 25.6, 28.5, 26.3,
                 21.3, 35.1, 37.8, 45.1, 28.5, 47.6, 33.9, 21.5, 34.3, 14.2,
                 40.9, 17.9, 44.9, 44.2, 20.5, 30.8, 43.0, 24.5, 20.1, 46.7,
                 49.6, 42.1, 19.8, 3.8, 0.2, 38.3, 21.3, 15.3, 11.2, 36.0], 555.5)

Try it online.

My Python skills are a bit rusty, so if you see any issues, let me know. Also, I think this can be improved in code for sure with some binary searches or something along those lines.

The program uses the Knapsack Meet-in-the-middle approach. It first uses all even-indexed items to get a set of all possible sums for the powerset of these even-indexed items. Then it does the same for all odd-indexed items, and simultaneously determines the minimum sum using the sums of these two sets.

Answer 2

Jelly, 10 bytes, Score \$O(2^n)\$

ŒPS€>Ƈ199Ṃ

Try it online!

Input is a list of prices for items. Output is the minimum possible price greater than 199. Note this outputs 199.20000000000002 due to floating point rounding. Also note as it stands that it will about the least total price greater than 199 (rather than greater than or equal to).

Time used scales exponentially and is approximately proportional to 2^n where n is the number of items. On TIO, 19 items takes approx. 14.5 seconds.