How should I tackle this real-life hypermarket problem?

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...

Topic market-basket-analysis data optimization

Category Data Science


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.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.