6
1
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 size10 <= 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 is199.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.
1
Welcome to PPCG! You'll have to specify what is the winning criterion for this challenge (the most common one is
– Arnauld – 2019-03-04T11:57:51.277code-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?@Arnauld I've modified the question but I have no idea whether it fits the rules now. – Saber – 2019-03-04T12:23:53.830
Yes, I think it does. Voted to reopen. – Arnauld – 2019-03-04T12:30:07.630
1
Please note however that
– Arnauld – 2019-03-04T12:36:53.833fastest-algorithm
(the tag you've chosen) doesn't meanfastest-code
(like your description suggests). I personally think thatfastest-algorithm
is indeed a better option here, so you'd rather edit the description than update the tag.@Arnauld OK, I've changed the description. If there is still something inappropriate can you help me correct it? I'm not very good at English ^ ^ – Saber – 2019-03-04T14:54:38.477
If two submissions have the same complexity, perhaps you should add a tiebreaker, such as shortest code. – Loovjo – 2019-03-04T19:26:43.707
Could we get a few more test cases please? – Quintec – 2019-03-04T19:54:01.223
2The 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. – Erik the Outgolfer – 2019-03-04T19:57:05.310
2Clarification 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. – Erik the Outgolfer – 2019-03-04T19:58:40.773
This would be simple knapsack if not for doubles... darn – Quintec – 2019-03-04T21:59:49.370
@Erik the Outgolfer I've changed the question. Now you can only output the total price, not products. – Saber – 2019-03-05T01:33:41.963
4Since 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. – tsh – 2019-03-05T03:19:11.267
@tsh 3Q very much .i Know how to do it now. – Saber – 2019-03-05T04:02:57.547
Here the problem seems to me exponential... The clue of a good algo could be only have less operations on a random array... (but this is difficult to prove) so remain only the code golf tag – RosLuP – 2019-03-05T08:10:47.163