Most Sets Achievable

[86trueno]

Hi All,

Please find attached excel database. I am trying to find the most number of "Sets" with a group of "Items" based on the following conditions:-

a) Must choose 6 Items.
b) In order for a Set to be considered eligible, the total sum of the 6 Items under a Set must equal to 4 or higher.

Thanks in advance.

[AliGW]

Welcome to the forum!

I think we shall need a little more guidance regarding the sample workbook - how exactly does it relate to your request? More detail, please. What is your expected output, for instance? And where has this been mocked up in the workbook?

[86trueno]

Hi,

Thanks for the swift response.

What i am trying to achieve is to obtain the most optimum combination of Items which can provide the most Sets (with a Sum of 4 or higher).

For instance if i were to choose Items FM, BSB, DC,BS, SSL & TD, i would be able to achieve 4 Sets (i.e. A,B,C & J). I found these combination of sets through lots of trial and error.

I am wondering if anyone know an easier way to find the most optimum combination of Items based on the conditions.
a) Must choose 6 Items.
b) In order for a Set to be considered eligible, the total sum of the 6 Items under a Set must equal to 4 or higher

I hope i am clear.

Many thanks in advance.

[shg]

What's the genesis of the problem and the value in its solution?

Why not pick all of the items and all of the sets that have four or more items?

How do you evaluate the merit of a given solution?

[GeoffW283]

In the interim, pending clarification s per shg's comment, here is a partial solution to the problem as originally stated:

First there are a couple of duplicates in the "Item" column: BS appears twice as does FS although I don't think that impacts the problem as stated assuming these should be distinct names.

Choosing 6 from 68 is probably too many combinations to exhaustively examine in a reasonable time, so I chose a Monte Carlo method, randomly choosing sets of 6 items and checking each combination for >= 4 Sets. This method found a number of sets of four, for example:
FM, HP, AS, BS, PD, SF: ==> B, C, I, SF
FM, BSB, DC, BS, HM, SS ==> C, H, J, M
FM, BSB, DC, BS, DT, FS ==> B, C, F, J

I ran the calculations for about 10 minutes and found no sets greater than 4.

Here's the details of what I did:

Column D contains 6 "y"s for the set of 6 to be tested. I set D3 to always be "y" as it has a "1" in the vast majority of columns. The worksheet is already sorted in order of the most "appearances" in a given row, so I arbitrarily chose to cut off my tests at D17 as higher rows have 3 or less "appearances. I randomly choose five columns from D4:D17 using the following in D4 copied down to D17:

Please Login or Register  to view this content.

The idea is to have the "y"s evenly distributed throughout the range - not sure I have that totally correct, but it seems to work well enough.

E73:AE73 sums the 1's for the 6 selected items for each set: e73 copied across:

Please Login or Register  to view this content.

D72 is set to the goal number of sets we're searching for (5 for example).
D73 is the actual number of sets found for the current combination of 6 items.

At this point it is possible to keep pressing F9 "recalculate" while watching cell D73. But easier on the finger, the following few lines of VBA automate the recalculation and stop the recalculations if the goal is met.

Please Login or Register  to view this content.

[shg]

Macro trueno in the attachment ratchets through all the combinations in about 25 minutes to arrive at

	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	AA	AB	AC	AD
1		Total	2	2	4	1	1	1	1	4	0	4	0	0	4	0	0	0	0	1	0	0	1	0	0	0	0	0	0	4
2
3	Items\Sets	Select	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z	AA
5	BSB	1	1		1			1		1		1
6	DC	1		1	1				1	1		1
9	BS	1		1	1							1			1
12	FC	1			1		1								1								1
13	HM	1								1		1			1					1
16	SS	1	1			1				1					1

The Monte Carlo approach is not a bad alternative.