0
$\begingroup$

I registered myself in the payback program of the hypermarket I am going to.

  • For every 2$ I get 1 point.

  • I buy the same products every week (Feta 2.19\$, Milk 0.99$, ...).

  • I visit only in weekdays.

I would like to maximize the amount of points I gather, while I also maximize the times I visit that hypermarket (so buying all the stuff at once is an awful solution).

How should I go about modeling this real-life situation in terms of a Data Science problem in the first place? If you feel like it, suggest an approach of tackling it as well...

$\endgroup$
  • $\begingroup$ Your second condition is a little confusing compared to what you going to do. What does it mean "maximize the times you visit hypermarket, while you going to visit only on weekdays? it needs some more conditions to fetch real life. For example - the limit of items to buy, the limit of money to spend, the limit of weight to care at ones as well as the weight of each product you going to buy, or its price... got it? $\endgroup$ – AlexR Mar 9 at 21:42
  • $\begingroup$ Hey AlexR, the set of items I buy every week is fixed (every week I buy feta, mlik, etc.). I can visit the market only on weekdays. Visiting without buying something is a no-go. I am a single guy, I am not buying that much stuff to worry about weight etc... $\endgroup$ – gsamaras Mar 10 at 11:32
2
$\begingroup$

Question

I feel that the question needs to be reformulated for clarity to:

Given a fixed set of purchased products $S=\{s_i\}$ with associated prices $p_i$, find the greatest number of disjoint subsets $S_1, S_2, etc$ such that the number of reward points attained in each subset equals the number of points attained for the whole.

A reward point is obtained for every whole number of 200 cents divisible into the total price of the set.

In other words you have a set of products that you will definitely buy then the maximal number of points you can acquire from those purchases is $floor(\frac{1}{200}\sum_i p_i)$. Since you cannot acquire more points than this any subdivisions you make, representing different trips to the hypermarket, need to reach the same amount of points.

Answer

The brute force way of considering every possible combination will be an exponential time algorithm. So you probably need to develop an algorithm which uses greedy approaches.

For example, one such approach would be to identify subsets. Say you had four products:
{milk, cheese, bread, oilves} with prices {189c, 200c, 211c, 205}, possible 4 reward points,
then a preliminary scan (over a single item) to detect prices with zero residuals will return two disjoint sets; {cheese} and {milk, bread, olives}. Now you can recursively treat the 3-set as the same problem, in this case no single product has a multiple of 200, but milk and bread does sum to 400 so that is a perfect split: {cheese} and {milk. bread} and {olives}
And you have arrived at the result.

In general you cannot know how many products might be needed in a combination to make a perfect multiple of 200, but you can use some heuristics derived from your initial set. In this case $\sum_i p_i mod 200 = 805 mod 200 \equiv 5$, so you know that you cannot have the sum of residuals of subgroups totalling more than 5 otherwise your solution returns less reward points.

For example if you grouped {cheese, bread} you get 2 reward points with a residual of 11 cents. There is no combination of the remaining {milk, olives} that can collect 2 more reward points. In that case the residual is 194 cents, which actually suggests the two disjoint sets can be combined to produce an additional reward point since 11 + 194 > 200.

PS

I have no idea why you mention weekdays without giving any information about their significance to the problem. Unless you want me to assume that you only visit the hypermarket once per day in which case the total number of disjoint subsets you can have is 5.

$\endgroup$
  • $\begingroup$ Yes, I visit the hypermarket only once per day, thanks! $\endgroup$ – gsamaras Mar 10 at 11:42

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.