How to implement such an algorithm?
Say there are x number of boxes, each box contains an "inventory" of the letters A-Z, with each letter inventory being 1 or more.
Now say I need 开发者_运维问答the following:
- 6 As
- 2 Bs
- 1 C
How do I get a list of all the possible combination/permutation of boxes that can provide me with the letters I need?
The algorithm needs to also produce combination of boxes to meet my requirements. For example: say Box-1 only has 4 As and Box-2 has 1 A and Box-3 has 1 A, I need the result of the algorithm to specify that the 6 As can be fulfilled across the 3 boxes.
What is the basic logic to the solution of such a problem. Are there any particular algorithms I need to be looking into for this?
EDIT 1:
Per dcp's suggestion, here's is my attempt that the PHP implementation:
$boxes = array(
// box 1
array(
'A' => 6,
'B' => 4,
'C' => 10
),
// box 2
array(
'A' => 8,
'B' => 4,
'C' => 2
),
// box 3
array(
'A' => 1,
'B' => 1,
'C' => 0
)
);
$n = count($boxes);
for ($mask = 0; $mask <= (1 << $n) - 1; $mask++)
{
$tots = array();
for ($i = 0; $i < $n; $i++)
{
if (((1 << $i) & $mask) != 0)
{
// this is a selected box for this mask, add the A's, B's etc. for this box to the total
$tots[0] += $boxes[$i]['A'];
$tots[1] += $boxes[$i]['B'];
$tots[2] += $boxes[$i]['C'];
}
// check the tots array to see if it meets the letter requirements. If it does,
// then this is a valid combination of boxes.
}
}
If the number of boxes is fairly small, say 25 or less, then you could use a bitmask to brute force over all the possible box combinations:
// assume n is number of boxes, and boxes is the array of boxes
for(int mask = 0; mask <= (1<<n)-1; ++mask) {
int tots[26];
for(int i = 0; i < n; ++i) {
if ( ((1<<i)&mask) != 0 ) {
// this is a selected box for this mask, add the A's, B's etc. for this box to the total
tots[0] += number of A's in box i
tots[1] += number of B's in box i
.
.
}
// check the tots array to see if it meets the letter requirements. If it does,
// then this is a valid combination of boxes.
}
}
精彩评论