大理石分割问题的动态规划解决方案

大理石分割(动态规划)

有若干块大理石，其大小及美观程度不一，为了比较客观的分割这些大理石，我们需要先给这些大理石一个评分，评分分为6个等级，分别用1~6的数字来表示。现希望将这些大理石分成两部分，使每部分的评分之和相同。
输入：
输入一行，包括6个数，分别是每个等级的大理石的数量。每种等级的大理石数量不超过20000.
输出：
如果这些大理石能否分割成评价等级之和相同的两部分，则输出true，否则输出false.
样例输入：
1 0 1 2 0 0
样例输出：
false

算法分析

试想如果可以分配，那么是否可以找到一种分配方案使得使用得大理石数量最少。如此，该问题，就变成了货币兑付问题。
就该问题，以score【6】来保存各等级大理石得输卵不过，均值avg=sum/2=6；所以后面以用6种面值得货币（大理石）来兑付avg价值的货币来进行描述：
动态规划表如下表所示：

其中最左列表示0-6种纸币，其价值分别为0-6，行为0-avg的价值的纸币需要兑付的，因为其中avg为6.
首先初始第2列为0，第一行为∞。数量不够即表示该价值的纸币不能被兑付以无穷表示。
现在开始填第3行，首先填第3行3列即v【1，1】，用前1种纸币来兑付价值为1的纸币，第一种其数量可选为0-1，当为0时，使用的数量为0+V【0，1-01】=∞，当为1时，使用的数量为1+V【0，1-11】=1。故V【1，1】=1，同理v[1,2]时，第1种货币的数量仍为0-1，当为0时，使用的数量为0+V【0，2-01】=∞，当为1时数量为1+V