How do I efficiently partition a set of item pairs with varying quantities
up vote
0
down vote
favorite
Apologies in advance if my terminology is off. I'm not a mathematician (just a programmer).
I have a set of item pairs (a shopping cart) where each item has a quantity
1x item A
1x item B
2x item C
1x item D
1x item E
I have a discount code that requires a minimum quantity of items in the cart in order to be applicable. The goal is to maximize the discount.
If the minimum was 3 items, there would be two candidates for this cart:
(A, B, C, D, E) = $50 discount
(A, B, C) (C, D, E) = $60 discount (since we can use 'C' twice)
Rather than brute-forcing it, is there an algorithm used for calculating the optimal way to partition sets of pairs like these? Or even a hint of a branch of maths I should be looking into?
Thanks in advance for any insight.
algorithms
asked Nov 14 at 23:05
Alex Dunae
1011
add a comment |
up vote
0
down vote
favorite
Apologies in advance if my terminology is off. I'm not a mathematician (just a programmer).
I have a set of item pairs (a shopping cart) where each item has a quantity
1x item A
1x item B
2x item C
1x item D
1x item E
I have a discount code that requires a minimum quantity of items in the cart in order to be applicable. The goal is to maximize the discount.
If the minimum was 3 items, there would be two candidates for this cart:
(A, B, C, D, E) = $50 discount
(A, B, C) (C, D, E) = $60 discount (since we can use 'C' twice)
Rather than brute-forcing it, is there an algorithm used for calculating the optimal way to partition sets of pairs like these? Or even a hint of a branch of maths I should be looking into?
Thanks in advance for any insight.
algorithms
asked Nov 14 at 23:05
Alex Dunae
1011
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Apologies in advance if my terminology is off. I'm not a mathematician (just a programmer).
I have a set of item pairs (a shopping cart) where each item has a quantity
1x item A
1x item B
2x item C
1x item D
1x item E
I have a discount code that requires a minimum quantity of items in the cart in order to be applicable. The goal is to maximize the discount.
If the minimum was 3 items, there would be two candidates for this cart:
(A, B, C, D, E) = $50 discount
(A, B, C) (C, D, E) = $60 discount (since we can use 'C' twice)
Rather than brute-forcing it, is there an algorithm used for calculating the optimal way to partition sets of pairs like these? Or even a hint of a branch of maths I should be looking into?
Thanks in advance for any insight.
algorithms
asked Nov 14 at 23:05
Alex Dunae
1011
Apologies in advance if my terminology is off. I'm not a mathematician (just a programmer).
I have a set of item pairs (a shopping cart) where each item has a quantity
1x item A
1x item B
2x item C
1x item D
1x item E
I have a discount code that requires a minimum quantity of items in the cart in order to be applicable. The goal is to maximize the discount.
If the minimum was 3 items, there would be two candidates for this cart:
(A, B, C, D, E) = $50 discount
(A, B, C) (C, D, E) = $60 discount (since we can use 'C' twice)
Rather than brute-forcing it, is there an algorithm used for calculating the optimal way to partition sets of pairs like these? Or even a hint of a branch of maths I should be looking into?
Thanks in advance for any insight.
algorithms
algorithms
asked Nov 14 at 23:05
Alex Dunae
1011
asked Nov 14 at 23:05
Alex Dunae
1011
asked Nov 14 at 23:05
Alex Dunae
1011
asked Nov 14 at 23:05
Alex Dunae
1011
asked Nov 14 at 23:05
Alex Dunae
1011
1011
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48
add a comment |
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998938%2fhow-do-i-efficiently-partition-a-set-of-item-pairs-with-varying-quantities%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
It's not clear how this is being assigned, is it $10 per unique item in a subgroup?
– Ian
Nov 14 at 23:06
Yes, exactly. $10 per item in a subgroup. And an item will only appear once per subgroup.
– Alex Dunae
Nov 14 at 23:21
What do you mean by pairs? I only see two of one thing, that is C. You have to specify the rules. It appears that you cannot apply the discount to two of the same item in a group. You can simply make groups of $3$, starting with the most common items. If you have one or two left over, add them into some group. That gets every item into a group as long as there are at least $3$ and not to many of one kind. What is wrong with that? That will help clarify the question.
– Ross Millikan
Nov 15 at 0:48