Ecological Bin Packing

题意翻译

装箱问题,或者将某些重量的物品放入不同的箱子的问题。这是一个历史上有趣的问题。一些装箱问题是NP完全的,但是适合动态规划解决方案或近似最优的启发式解决方案。 在这个问题上,你将解决处理回收玻璃的垃圾箱包装问题。回收玻璃要求玻璃根据颜色分为三类:棕色,绿色和透明的。在这个问题上,你会得到三个回收箱,每个包含指定数量的棕色,绿色和透明瓶子。为了回收,瓶子将需要被移动,使得每个垃圾桶只包含一种颜色的瓶子。 问题是要减少移动瓶子的数量。你可以假设唯一的问题是尽量减少箱子之间的移动次数。就这个问题而言,每个垃圾箱的容量都是无限的,唯一的限制就是移动瓶子,使每个垃圾桶都包含单一颜色的瓶子。瓶的总数永远不会超过2^31 感谢耀晨_wcx提供翻译

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38 [PDF](https://uva.onlinejudge.org/external/1/p102.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA102/ef84892469f793327bfb4a3ea04e4237b1761a6d.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA102/ae3b90e524e6ffd7e27eab05a64abfd8be7111ef.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA102/249702f9f5f1e91446cb32d9b3ad6a7eca7264f5.png)

输入输出样例

输入样例 #1

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

输出样例 #1

BCG 30
CBG 50