6
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! You'll have to specify what is the winning criterion for this challenge (the most common one is code-golf but many others exist). I'd also recommend to include the solution for the given example and add a few other test cases. Also, can a product be purchased more than once? Is the total price supposed to be displayed before or after discount? \$\endgroup\$ – Arnauld Mar 4 at 11:57
  • 1
    \$\begingroup\$ Please note however that fastest-algorithm (the tag you've chosen) doesn't mean fastest-code (like your description suggests). I personally think that fastest-algorithm is indeed a better option here, so you'd rather edit the description than update the tag. \$\endgroup\$ – Arnauld Mar 4 at 12:36
  • 2
    \$\begingroup\$ The Input section of your challenge says "All the prices above". This might look like we can simply hardcode the output, as the input is constant, but I guess you don't want that. I suggest writing something like "A list of products and their prices, such as the above example.". Also, the line above the code block reads "Here are the products:"; I suggest changing that to "Here's an example list of products:". More test cases will be appreciated too. Finally, I suggest allowing the solutions to identify the products in a different way than the uppercase letters, e.g. 0- or 1-based indices. \$\endgroup\$ – Erik the Outgolfer Mar 4 at 19:57
  • 2
    \$\begingroup\$ Clarification of the above comment (comments have a character limit): I'd also suggest not having the solutions unnecessarily take IDs of the products (they might not use them and it may cost to clean the input of them, although that will most probably be an O(number of products) operation), they can be based on the order they're given. \$\endgroup\$ – Erik the Outgolfer Mar 4 at 19:58
  • 4
    \$\begingroup\$ Since the subset sum problem could be reduced to this question. This question is NP-Hard. And this question may be reduced to knapsack problem by making weight = price, max_weight = sum(price) - discount_price. Knapsack problem had been will well learnt, so I won't expect there will be any interesting answers here. \$\endgroup\$ – tsh Mar 5 at 3:19
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Just curious - why did you pick python? \$\endgroup\$ – Quintec Mar 6 at 1:51
  • \$\begingroup\$ @Quintec Multiple reasons actually. When I was searching for an appropriate algorithm I came across a solution in Python for subsets which sum to a target exactly, which I modified to a meet-in-the-middle approach first, and then to a knapsack approach. The other two reasons are that Python's performance is pretty good overall (although Java is too tbh), and I want to try some languages I don't use very often once in a while (like I did yesterday with an Elixir answer). \$\endgroup\$ – Kevin Cruijssen Mar 6 at 7:39
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Arnauld sorry missed that. I've added info about both absolute time and scaling of time to list length. The provided example is very quick (~0.2 seconds), but it approximately doubles for each added item. \$\endgroup\$ – Nick Kennedy Mar 4 at 22:47
  • \$\begingroup\$ @NickKennedy Score is complexity, not bytes, so you need to change the header. Also 2^n isn't particularly good :P \$\endgroup\$ – ASCII-only Mar 4 at 22:48
  • \$\begingroup\$ @ASCII-only Yes, realised that. I saw the first comment from Arnauld about the choice of scoring metric (such as code-golf) and misread that as being what the OP had chosen. \$\endgroup\$ – Nick Kennedy Mar 4 at 22:50
  • \$\begingroup\$ btw score as "\$O(2^n)\$" is fine (or maybe even preferable) \$\endgroup\$ – ASCII-only Mar 4 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.