本文共 2710 字,大约阅读时间需要 9 分钟。
问题描述:假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许m张邮票。连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,即在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5和m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1-70。
分析:
对于连续邮资问题,用n元组x[1:n]表示n种不同的邮票面值,并约定它们从小到大排列。x[1]=1是惟一的选择。此时的最大连续邮资区间是[1:m]。 x[2]的可取值范围是[2:m+1]。 在一般情况下,已选定x[1:i-1],最大连续邮资区间是[1:r],则x[i]的可取值范围是[x[i-1]+1:r+1]。算法设计:
package com.bean.algorithmbasic;public class StampsDemo2 { /* 连续邮资问题: 假设国家发行了n种不同面值的邮票,并且规定每张信封上最多只允许贴m张邮票。 连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计, 在一张张信封上可以贴出从邮资1开始,增量为1的最大连续邮资区间。 举例分析: 当n=2,m=3时,如果面值分别为1和4,则可以获得的邮资范围为1~6 加上 8 , 9 , 12。但是8,9,12已经是不连续的和了。 如果面值为1,3,则可以获得1~7之间的每个邮资值,并且7就是可以得到的连续的邮资最大值。 前解,递归调用 , 回溯 输入: 2 2 3 5 4 输出: 7 1 3 70 1 3 11 15 32 */ static final int NUM=10; static final int LEN=10000; static int[] x = new int[NUM]; static int cnt = 0;//当前邮票种类 static int[] r = new int[NUM];//用于面值结果 static int max = 0;//最大值 static int[][] C = new int[NUM][LEN]; //记录搜索结点状态 /* * 计算当前邮票面值的最大连续邮资区间 * */ public static int findMax(int knd, int lim) { int j = 1; while (C[cnt - 1][j]!=0) { if (j < x[cnt] || C[cnt - 1][j] <= C[cnt][j - x[cnt]] + 1) C[cnt][j] = C[cnt - 1][j]; else C[cnt][j] = C[cnt][j - x[cnt]] + 1; j++; } while (true) { int tmp = Integer.MAX_VALUE; for (int i = 1; i <= cnt; i++) { if (tmp > C[cnt][j - x[i]] + 1) tmp = C[cnt][j - x[i]] + 1; } if (tmp == Integer.MAX_VALUE || tmp > lim) break; else C[cnt][j] = tmp; j++; } C[cnt][j] = 0; return j - 1; } public static void dfs(int type,int limit) { if (cnt == type) { if (x[cnt] * limit < max) return; int tmp = findMax(type,limit); if (tmp > max) { max = tmp;//若比记录的最大连续邮资区间上限大,则更新 for (int i = 1; i <= type; i++) //记录新的邮票面值组合 r[i] = x[i]; } } else { int tmp = findMax(type,limit); for (int i = tmp + 1; i >= x[cnt] + 1; i--) { x[++cnt] = i;//将可能面值加入当前面值组合中 dfs(type,limit); cnt--; } } } public static void main(String args[]){ int limit=3; //允许贴4张邮票 int type=2; //面值有5种 //从面值1开始,必须得有1,否则很多数值都不能构成。 x[1] = 1; //因为面值1是第一种,所以cnt=1 cnt = 1; dfs(type,limit); System.out.println("MAX = "+max); for (int i = 1; i <= type; i++) { System.out.println(r[i]+" "); } }}
(完)
转载地址:http://vgvdi.baihongyu.com/