selection on fly

[mrajanikrishna]

Dear Friends,

I am having strange problem. I have a set with different sizes(in
KB). Ex. 66 KB, 25 KB
I am getting another set from database which also having different
sizes. Ex. 20 KB, 14 KB, 35 KB,12 KB, 6 KB

I want take a decission which combination is best fit to 66 KB and
which combination to 25 KB sets. I want to fully utilise the space in
both sets(66 KB and 25 KB).

Can anybody give an idea or an example?

Any reply is highly appreciated. Thanks in advance

[mrajanikrishna]

Hi Ciaran,

Thank you very much for the reply.

Ciaran O''Donnell wrote:

Thinking about your previous question, This doesnt work out what containers
are needed, just how to arrange them to waste the least space. you would need
to change it to try through a set of List<holdingset>'s in accending price
order to get the cheapest shipping.
--

Ciaran O''Donnell
http://wannabedeveloper.space.live.com
"Ciaran O''Donnell" wrote:

I saw a question like this a while ago and had an idea but didnt have time to
investigate. My idea was to work out all the permutations of filling the
holding sets (storage containers for clothes in the last example) and working
out which wasted the least space. I have spent about an hour implementing
this for you (with help for permutation logic) with some sample classes and
it seems to work. You will need to tidy it up and test it more thoroughly. It
is three classes, a holdingset and set and the setAllocator. you can call
DemoAllocateSets to run your example or AllocateSets with a pair of lists and
run it for real.

Let me know how it does for you and post up the fixed up version for the guy
with the chinese cloths factory.

class HoldingSet
{

public HoldingSet(string n, int s) { Name = n; _size = s; }

string _name;

public string Name { get { return _name; } set { _name = value; } }
private int _size;

public int Size
{
get { return _size; }
set { _size = value; }
}
private List<set_sets;

public List<setSets
{
get { return _sets; }
set { _sets = value; }
}

public int Total{
get{
int total=0;
for (int i = 0; i < _sets.Count; i++)
{
total+=_sets[i].Size;
}
return total;
}
}

public int GetWasted(){
return _size-Total;
}

}

class set
{
private string name;

public string Name
{
get { return name; }
set { name = value; }
}
private int size;

public int Size
{
get { return size; }
set { size = value; }
}
public set(string n, int s) { name = n; size = s; }
}

class setAllocator
{

public void DemoArrangeSets()
{

List<HoldingSetholds = new List<HoldingSet>();
holds.Add(new HoldingSet("25hset", 25));
holds.Add(new HoldingSet("66hset", 66));

List<setsets = new List<set>();
sets.Add(new set("20set", 20));
sets.Add(new set("14set", 14));
sets.Add(new set("35set", 35));
sets.Add(new set("12set", 12));
sets.Add(new set("6set", 6));

ArrangeSets(holds, sets);
}
public void ArrangeSets(List<HoldingSetholds, List<setsets)
{
holds.Sort(new Comparison<HoldingSet>(delegate(HoldingSet set1, HoldingSet
set2) { return ((IComparable)set1.Size).CompareTo(set2.Size); }));
sets.Sort(new Comparison<set>(delegate(set set1, set set2) { return
((IComparable)set1.Size).CompareTo(set2.Size); }));

int[] indexesForPerm = new int[sets.Count];
for (int i = 0; i < sets.Count; i++)
{
indexesForPerm[i]=i+1;
}
List<setcurrentPermutation = new List<set>(sets);

List<setbestOrder = new List<set>(currentPermutation);
int bestwaste = int.MaxValue;
int select = sets.Count;
int number = select;
while (true)
{

// for this combination, list permutations in lexicographical order

while (get_next(currentPermutation, select))
{
AssignSets(holds, currentPermutation);
int waste = int.MaxValue;
holds.ForEach(new Action<HoldingSet>(delegate(HoldingSet hset) { waste
+= hset.GetWasted(); }));
if (waste < bestwaste)
{
bestwaste = waste;
bestOrder = new List<set>(currentPermutation);
}

}
// generate next combination in lexicographical order
int i = select - 1; // start at last item

while (i >= 0 && indexesForPerm[i] == (number - select + i + 1)) // find
next item to increment
--i;

if (i < 0) break; // all done
++indexesForPerm[i]; // increment

for (int j = i + 1; j < select; j++) // do next combination
indexesForPerm[j] = indexesForPerm[i] + j - i;
currentPermutation = new List<set>();
foreach (int x in indexesForPerm)
{
currentPermutation.Add(sets[x]);
}
}
AssignSets(holds, bestOrder);

holds.ToString();

}

void AssignSets(List<HoldingSetholds, List<setcurrentPermutation)
{
holds.ForEach(new Action<HoldingSet>(delegate(HoldingSet h) { h.Sets = new
List<set>(); }));

int setindex = 0;
for (int i = 0; i < holds.Count; i++)
{
int total = holds[i].Total;
int size = holds[i].Size;
while (setindex < currentPermutation.Count && total +
currentPermutation[setindex].Size < size)
{
total += currentPermutation[setindex].Size;
holds[i].Sets.Add(currentPermutation[setindex]);
setindex++;
}
if (setindex == currentPermutation.Count) break;

}
}

void swap(List<setcurrentPermutation, int a, int b)
{
set temp = currentPermutation[a];
currentPermutation[a] = currentPermutation[b];
currentPermutation[b] = temp;
}

bool get_next(List<setcurrentPermutation, int k)
{
int i = k - 1;
while (i >0 && currentPermutation[i - 1].Size >= currentPermutation[i].Size)
i--;

if (i < 1) return false; // all in reverse order

int j = k;
while (j >0 && currentPermutation[j - 1].Size <= currentPermutation[i -
1].Size)
j--;

swap(currentPermutation, i - 1, j - 1);

i++;
j = k;

while (i < j)
{
swap(currentPermutation, i - 1, j - 1);
i++;
j--;
}

return true;
}
}
--

Ciaran O''Donnell
http://wannabedeveloper.space.live.com
"mr************@gmail.com" wrote:

Dear Friends,
>
I am having strange problem. I have a set with different sizes(in
KB). Ex. 66 KB, 25 KB
I am getting another set from database which also having different
sizes. Ex. 20 KB, 14 KB, 35 KB,12 KB, 6 KB
>
I want take a decission which combination is best fit to 66 KB and
which combination to 25 KB sets. I want to fully utilise the space in
both sets(66 KB and 25 KB).
>
Can anybody give an idea or an example?
>
Any reply is highly appreciated. Thanks in advance
>
>