A Tricky Dilemna

[stioffan]

Hello,

I need a hand with the following problem as I have not used Excel for
quite a while.

--------There are 4 categories of goods - A,B,C,D
--------Each category has 100 goods/supplies that range in price from
$4.00 -$26.00(cents are inclusive: ie - one particular item in category
A costs $15.41)
--------A certain # of goods must be chosen from each category as
follows:
A - 3
B - 4
C - 3
D - ONLY 1 ITEM IS NEEDED FROM THIS CATEGORY.

HERE IS THE TRICKY PART:

A buyer must select the exact number of goods required from each
category and
the total cost of all 11 chosen goods cannot exceed $100.00 nor can it
be below $99.00.

So is there a way to get excel to do this and display what goods were
chosen?
I also figure that there will be more than one set of 11 goods that can
fit the answer,(maybe 100s of answers) so is there also a way of showing
all possible combinations?

Thanks in advance to all of you who respond my email is
(e-mail address removed)

 

[Jack Handey]

Are you actually in an algebra class and you're trying to get us do your
homework?

 

[stioffan]

Sorry to dissappoint Jack. I've made it through Differential Equations
but that was 15 years ago. I just need a hand with this. My work doe
not involve me using excel (I'm not a receptionist, nor an accountant)
and I have never been adept at programming in Excel (or any othe
program for that matter).

So can you help, or are you going to make me suffer?

Stioffa

 

[Harlan Grove]

stioffan wrote...

I need a hand with the following problem as I have not used Excel for
quite a while.

--------There are 4 categories of goods - A,B,C,D
--------Each category has 100 goods/supplies that range in price from
$4.00 -$26.00(cents are inclusive: ie - one particular item in category
A costs $15.41)
--------A certain # of goods must be chosen from each category as
follows:
A - 3
B - 4
C - 3
D - ONLY 1 ITEM IS NEEDED FROM THIS CATEGORY.

HERE IS THE TRICKY PART:

A buyer must select the exact number of goods required from each
category and the total cost of all 11 chosen goods cannot exceed
$100.00 nor can it be below $99.00.

So is there a way to get excel to do this and display what goods were
chosen? I also figure that there will be more than one set of 11 goods
that can fit the answer,(maybe 100s of answers) so is there also a way
of showing all possible combinations?

This is what's called a knapsack problem. This class of problem has no
solution other than exhaustive analysis of all possible combinations.
In this case, there are 4 categories each with 100 goods, but at least
the number of goods in each category is limited as you specify. So the
number of possible combinations of goods you'd need to check would be

(100 choose 3) * (100 choose 4) * (100 choose 3) * 100 =
10,252,783,874,025,000,000

Even if you had a computer that could check a billion of these
combinations per second, it'd take over 300 years to check all the
combinations. This is why this class of problem is considered
unsolvable in practical terms.

You could use Solver to come up with one solution. Search the Google
Groups archives for the procedure to do so (Tushar Mehta and Dana
DeLouis have both posted directions for how to do so). However, listing
all such combinations of goods is a practical impossibility even using
Solver (or any other currently existing software). Since there have
been hundreds of computer science PhDs who've failed to come up with an
elegant solution to this problem over the past 5 decades, don't get
your hopes up that anyone else will give you a simple Excel approach to
do this.

 

[kcc]

Hello,

I need a hand with the following problem as I have not used Excel for
quite a while.

--------There are 4 categories of goods - A,B,C,D
--------Each category has 100 goods/supplies that range in price from
$4.00 -$26.00(cents are inclusive: ie - one particular item in category
A costs $15.41)
--------A certain # of goods must be chosen from each category as
follows:
A - 3
B - 4
C - 3
D - ONLY 1 ITEM IS NEEDED FROM THIS CATEGORY.

HERE IS THE TRICKY PART:

A buyer must select the exact number of goods required from each
category and
the total cost of all 11 chosen goods cannot exceed $100.00 nor can it
be below $99.00.

So is there a way to get excel to do this and display what goods were
chosen?
I also figure that there will be more than one set of 11 goods that can
fit the answer,(maybe 100s of answers) so is there also a way of showing
all possible combinations?

Thanks in advance to all of you who respond my email is
(e-mail address removed)

At 4 groups and 100 goods per group, you have 400 variables which is
double the limit that excel's solver can handle. There are add-ins you
can buy to handle it but they generally cost a few thousand dollars.
kcc