UVa 102

From Algorithmist
Jump to navigation Jump to search

102 - Ecological Bin Packing[edit]

Summary[edit]

The small constraints make Bruteforce/Exhaustive Search feasible, and it's trivial to take the best of the rest.

EDITED BY-ASAD(MBSTU(IT-14053)----------------------------- There three bin(in prblem) 1. first three integer represent the number of brown ,Green and clean glass in bin1 2. second three integer represent the number of brown ,Green and clean glass in bin2 3. third three integer represent the number of brown ,Green and clean glass in bin3

Now our task , minimum move to same colored glass in one bin.

We discuss only one case: 1 2 3 4 5 6 7 8 9 Bin1 : 1+2+3=6; Bin2: 4+5+6=15 Bin3: 7+8+9=24 [note: total=45] You have to calculate below sequence [it is must, because more minimum combination will find. So combination of color glass in Bin: BCG,BGC,CBG,CGB,GBC,GCB]

1.If we want to take brown glass in bin1, clean in bin2 & green in bin3[BCG] Bin1: We have to move 3 clean & 2 green glass from bin1; so move=2+3=5 Bin2: We have to move 4 brown & 5 green glass from bin2 ;so move=4+5=9 Bin3: We have to move 7 brown & 9 clean glass from bin3 ; so move=7+9=16 Total move=5+9+16=30 [note: 45-1-6-8=30]

2.If we want to take brown glass in bin1, green in bin2 & clean in bin3[BGC] Bin1: We have to move 3 clean & 2 green glass from bin1; so move=2+3=5 Bin2: We have to move 4 brown & 6 clean glass from bin2 ;so move=4+6=10 Bin3: We have to move 7 brown & 8 green glass from bin3 ; so move=7+8=15 Total move=5+10+15=30 [note: 45-1-5-9=30]

3. CBG:bin1: move=1+2=3, bin2: move=11; bin3: 16 total move: 30 [note…] 4.CGB:bin1: move:3 ,bin2: move=10 ,bin3: move=17 ,total move= 30 [note …] 5.GBC: bin1: move:4 ,bin2: move=11 ,bin3: move=15,total move= 30 [note …] 6.GCB:bin1: move:4 ,bin2: move=9 ,bin3:17 move= ,total move= 30 [note …] So minimum move =30 for each combination of color glass in the bin

 So Answer: BCG 30 [BCG is alphabetically first]

Gotcha's[edit]

  • If there is more than one minimal solution, pick the one that comes lexicographically first.

Input[edit]

1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10

Output[edit]

BCG 30
CBG 50

Solution[edit]