最大连续邮资问题

时间：2011-01-28 来源：异影

　　假设一个国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票（允许贴多张相同面值的邮票，如可以贴m张面值为1的邮票，则邮资为m）。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。

例如，当n=5和m=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。

问题分析：

　　由于需要贴出从1开始的邮票，因此第一张邮票面值必然为1。接下来的问题是找出剩下的n-1张邮票的面值。

　　假设已经确定了前面n-1张邮票的面值，就拿题目中的例子来说，假设1,3,11和15这四个面值已经被确定，那么怎么确定第五个值呢？首先，我们需要找出第五个值的取值范围。首先找出下限，先不考虑得那么仔细，我们就把下限确定为16，即已确定的面值数中最大的加上1，这样即使m值为1，也可以满足在原来的基础上继续贴出连续邮资区间。然后再确定其取值上限，假设已确定区间的面值可贴出的邮资最大连续区间值中的最大值为max（如题目中的m=4，则1,3,11和15这四个面值可组合出的最大连续邮资值为34，因为35是无法组合出来的），那么该值的上限就应该为max+1，即能组合出的最大邮资的最大值加1，这样即使m值为1，也能在原来的基础上尽可能地增大最大连续邮资区间的长度。看到这里，如果我们要使用一个一维数组values来表示邮票的面值，就能保证values的值是随下标的增加而增加的，如values[0] = 1,values[1] =3。那么values[i]的取值范围就是[values[i-1]+1,max+1]。

　　对已经确定的邮票面值，假设1,3,11,和15是已经确定的，且已知m=4，那么组合1到34中的每一个值，都可能有多种组合方式，如3可以由一个3或3个1组合，4可以由3+1或1+1+1+1来组合。而对于这样的情况，当然是使用的邮票数越少越好，比如要组合出4，当然要优先选择3+1的方式，因为这样的话可使用的邮票数还有两张，当继续使用邮票的时候，就会尽可能提高连续区间的最大值。因此，我们可以使用一种方式来存放组合出某个数需要的最少邮票数，用一维数组leastStamps表示，约定leastStamps[i]的值为组合出i需要的最少邮票数，如leastStamp[4] = 2就表示组合出4需要的最少邮票数为2。

　　有了上述分析，接下来就是最核心的部分。考虑已经确定的邮票面值，和这些邮票面值能组合最大邮资区间的所有组合范围，比如3+1和1+1+1+1都能组合出4。假设使用一个集合A表示所有的组合情况，然后根据组合出的邮资值来对结合进行分割，假设A[i]表示能组合出i的所有组合情况，那么A[4] = {3+1,1+1+1+1}。这样A = A[1] U A[2]U…UA[n]。即所有子集的并集。然后考虑加入下一个数后对A[i]的影响，假设a是A[i]中的一个元素，如3+1是A[4]的一个元素。那么加入下一个数values[i+1]后，对a的影响就是values[i+1]的多次重复，增加了a能贴出的邮资，假设增加的数为5，那么在3+1的计基础上还可以最多使用两次元素，则可贴出的最大邮资为3+1+5+5（先不考虑连续）。a具有普遍性，不必要考虑a增加一个元素或减少一个元素后的情况，因为增加一个元素或减少一个元素后，它就是A中的另一个元素。

  1 package org.fantasizer.algorithms;
  2 
  3 /**
  4  * 最大连续邮资问题，回溯法
  5  * 
  6  * @author Marco Jee
  7  * @date 2010-12-17
  8  */
  9 public class StampCost {
 10 
 11     private final static int MAX_NM = 10;
 12 
 13     private final static int MAX_POSTAGE = 1024;
 14 
 15     private final static int INF = Integer.MAX_VALUE;
 16 
 17     private int n;// n种不同面值的邮票
 18     private int m;// 一封信最多帖m张邮票
 19 
 20     private int values[];// 从x[0]到x[i]表示当前已经确定的i+1个面值
 21     private int stamps[];// 求出来的邮票面值最终结果
 22     private int leastStamp[];// 存放能由当前面值贴出某个邮资使用的最少邮票。如y[10] = 1，表示贴出10只需要一张，就是10本身。
 23     private int maxStamp;// 满足条件的邮资最大区间的最终结果
 24     private int ranges;// 表示能由x贴出的最大连续区间
 25 
 26     public StampCost(int n, int m) {
 27         this.values = new int[MAX_NM];
 28         this.values[0] = 1;// 第一个永远是1
 29         this.stamps = new int[MAX_NM];
 30         this.leastStamp = new int[MAX_POSTAGE];
 31         this.n = n;
 32         this.m = m;
 33         this.ranges = m;// 初始为m，因为m个1就是m
 34         int i = 0;
 35         for (i = 0; i <= this.ranges; i++) {
 36             leastStamp[i] = i;
 37         }
 38         while (i < MAX_POSTAGE) {
 39             leastStamp[i++] = INF;
 40         }
 41         this.maxStamp = 0;
 42         // 第一张永远为1，所以从第二章开始计算
 43         this.backtrack(1);
 44     }
 45 
 46     /**
 47      * 从第(i+1)张邮票到第n张邮票的面值
 48      * 
 49      * @param i
 50      */
 51     public void backtrack(int i) {
 52         int tmp;
 53 
 54         // 如果到达发行邮票的张数，则更新最终结果值，并返回结果
 55         if (i >= this.n) {
 56             // 用r计算可贴出的连续邮资最大值，而maxStamp存放最终结果
 57             if (this.ranges > this.maxStamp) {
 58                 this.maxStamp = this.ranges;
 59                 // 用x[i]表示当前以确定的第i+1张邮票的面值，ans保存最终结果
 60                 for (tmp = 0; tmp < this.n; tmp++) {
 61                     this.stamps[tmp] = this.values[tmp];
 62                 }
 63             }
 64             return;
 65         }
 66 
 67         // 保存y和r值，避免递归调用时被更新。由于计算下一次时，y和r的值都需要改变，因此相当于是初始化
 68         int[] backupY = new int[MAX_POSTAGE];
 69         for (tmp = 0; tmp < MAX_POSTAGE; tmp++) {
 70             backupY[tmp] = this.leastStamp[tmp];
 71         }
 72         int backupR = this.ranges;
 73 
 74         int next;// 表示下一个邮票面值的可能值
 75         int postage;
 76         int num;
 77 
 78         // 在当前已确定的基础上，下一张邮票面值的取值范围为当前最大面值+1到当前可组合的连续邮资最大值+1
 79         for (next = values[i - 1] + 1; next <= ranges + 1; next++) {
 80             // 更新第i张的值
 81             this.values[i] = next;
 82 
 83             // 搜索当前已确定的邮票能表示出的最大邮资范围（最小值为0，最大值为邮票最大值乘以最大张数）
 84             for (postage = 0; postage < values[i - 1] * m; postage++) {
 85                 // 计算表示postage还可以使用的邮票数目
 86                 for (num = 1; num <= this.m - this.leastStamp[postage]; num++) {
 87 
 88             // 如果组合出postage的最少有票数加上num张，小于组合出postage+num*next的邮票数，说明组合出postage+num*next并不需要使用num张下一张邮票
 89                     // 那么组合出postage+num*next的邮票数，就等于组合出postage的邮票数加上num
 90                     if (this.leastStamp[postage] + num < this.leastStamp[postage
 91                             + num * next]
 92                             && (postage + num * next < MAX_POSTAGE)) {
 93                         leastStamp[postage + num * next] = leastStamp[postage]
 94                                 + num;
 95                     }
 96                 }
 97             }
 98 
 99             while (this.leastStamp[this.ranges + 1] != INF) {
100                 this.ranges++;
101             }
102 
103             // 递归调用求下一个值
104             backtrack(i + 1);
105 
106             this.ranges = backupR;
107             for (tmp = 0; tmp < MAX_POSTAGE; tmp++) {
108                 this.leastStamp[tmp] = backupY[tmp];
109             }
110         }
111     }
112 
113     public void print() {
114         for (int i = 0; i < n; i++) {
115             System.out.print(stamps[i] + " ");
116         }
117         System.out.println(":" + this.maxStamp);
118     }
119 
120     public static void main(String[] args) {
121         StampCost sc = new StampCost(5, 4);
122         sc.print();
123     }
124 }
125