题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108
类型: 回溯
原题:
The government of Nova Mareterrania requires that various legal documents have stamps attached to them so that the government can derive revenue from them. In terms of recent legislation, each class of
document is limited in the number of stamps that may be attached to it. The government wishes to know how many different stamps, and of what values, they need to print to allow the widest choice of values to be made up under these conditions. Stamps are always
valued in units of $1.
This has been analysed by government mathematicians who have derived a formula forn(h,k), wherehis the number of stamps that may be attached to a document,kis
the number of denominations of stamps available, andnis the largest attainable value in a continuous sequence starting from $1. For instance, ifh=3,k=2 and the denominations are $1 and $4, we can make all the values from $1 to
$6 (as well as $8, $9 and $12). However with the same values ofhandk, but using $1 and $3 stamps we can make all the values from $1 to $7 (as well as $9). This is maximal, son(3,2) = 7.
Unfortunately the formula relatingn(h,k) toh,kand the values of the stamps has been lost--it was published in one of the government reports but no-one can
remember which one, and of the three researchers who started to search for the formula, two died of boredom and the third took a job as a lighthouse keeper because it provided more social stimulation.
The task has now been passed on to you. You doubt the existence of a formula in the first place so you decide to write a program that, for given values ofhandk, will determine an optimum
set of stamps and the value ofn(h,k).
Input
Input will consist of several lines, each containing a value forhandk. The file will be terminated by two zeroes (0 0). For technical reasons the sum ofhandkis
limited to 9. (The President lost his little finger in a shooting accident and cannot count past 9).
Output
Output will consist of a line for each value ofhandkconsisting of thekstamp values in ascending order right justified in fields 3 characters wide, followed by a space and
an arrow (->
) and the value ofn(h,k) right justified in a field 3 characters wide.
Sample input
3 2
0 0
Sample output
1 3 -> 7
题目大意:
某国家发行k种不同面值的邮票,并且规定每张信封上最多只能贴h张邮票。 公式n(h,k)表示用从k中面值的邮票中选择h张邮票,可以组成面额为连续的1,2,3,……n, n是能达到的最大面值之和。例如当h=3,k=2时, 假设两种面值取值为1,4, 那么它们能组成连续的1……6, 虽然也可以组成8,9,12,但是它们是不连续的了。
分析与总结:
连续邮资问题,这个算是很经典的一个问题了。王晓东的《计算机算法设计与分析第三版》 p173有介绍, 但是讲的不够详细, 这里转载了一篇博客对王晓东讲的有更深入详细分析:
连续邮资问题http://blog.csdn.net/shuangde800/article/details/7755254
以下是按照我自己的话来总结:
首先开一个数组stampVal【0...i】来保存各个面值,再开一个maxVal[0...i]来保存当前所有面值能组成的最大连续面值。
那么,我们可以确定stampVal[0] 一定是等于1的。因为如果没有1的话,很多数字都不能凑成。
然后相应的,maxVal[0] = 1*h. h为允许贴邮票的数量
接下去就是确定第二个,第三个......第k个邮票的面值了,这个该怎么确定呢?
对于stampVal[i+1], 它的取值范围是stampVal[i]+1 ~maxVal[i]+1.
stampVal[i]+1好理解, 这一次取的面值肯定要比上一次的面值大, 而这次取的面值的上限是上次能达到的最大连续面值+1, 是因为如果比这个更大的话, 那么
就会出现断层, 即无法组成上次最大面值+1这个数了。 举个例子, 假设可以贴3张邮票,有3种面值,前面2种面值已经确定为1,2, 能达到的最大连续面值为6, 那么接下去第3种面值的取值范围为3~7。如果取得比7更大的话会怎样呢? 动手算下就知道了,假设取8的话, 那么面值为1,2,8,将无法组合出7 !!
知道了这个以后,就可以知道回溯的大概思路了, 但是还不够, 怎样取得给定的几个面值能够达到的最大连续面值呢?
最直观容易想到的就是直接递归回溯枚举所有情况, 便可知道最大连续值了。
下面是我写的递归函数:
// cur当前用了几张票, n面额数, sum面值之和
void dfs(int cur, int n, int sum){
if(cur >= h){
occur[sum] = true;
return;
}
occur[sum] = true;
for(int i=0; i<=n; ++i){
dfs(cur+1, n, sum+stampVal[i]);
}
}
occur是一个全局数组, 调用递归时先初始化为0。 然后用它来记录出现过的面值之和。
最后只需要从occur数组的下标1开始枚举,直到不是true值时就是能达到的最大连续面值。
由于这道题的数据量很小,所以这样做完全不会超时,速度也不错:
下面是用这种方法的代码:
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define MAXN 200
using namespace std;
int h, k;
int ans[MAXN], maxStampVal, stampVal[MAXN], maxVal[MAXN];
bool occur[MAXN];
// 计算给定面额和数量能够达到的最大连续面值
// cur当前用了几张票, n当前面额数, sum面额之和
void dfs(int cur, int n, int sum){
if(cur >= h){
occur[sum] = true;
return;
}
occur[sum] = true;
for(int i=0; i<=n; ++i){
dfs(cur+1, n, sum+stampVal[i]);
}
}
void search(int cur){
if(cur >= k){
if(maxVal[cur-1] > maxStampVal){
maxStampVal = maxVal[cur-1];
memcpy(ans, stampVal, sizeof(stampVal));
}
return ;
}
for(int i=stampVal[cur-1]+1; i<=maxVal[cur-1]+1; ++i){
memset(occur, 0, sizeof(occur));
stampVal[cur] = i;
dfs(0, cur, 0);
int num=0, j=1;
while(occur[j++]) ++num;
maxVal[cur] = num;
search(cur+1);
}
}
int main(){
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
// h数量, k面额数
while(scanf("%d %d", &h, &k), h+k){
stampVal[0] = 1;
maxVal[0] = h;
maxStampVal = -2147483645;
search(1);
for(int i=0; i<k; ++i)
printf("%3d", ans[i]);
printf(" ->%3d\n", maxStampVal);
}
return 0;
}
计算X[1:i]的最大连续邮资区间在本算法中被频繁使用到,如果数据量大的话,很可能就会超时了。
《计算机算法设计与分析第三版》给了一个更高效的方法:
考虑到直接递归的求解复杂度太高,我们不妨尝试计算用不超过m张面值为x[1:i]的邮票贴出邮资k所需的最少邮票数y[k]。通过y[k]可以很快推出r的值。事实上,y[k]可以通过递推在O(n)时间内解决:
for (int j=0; j<= x[i-2]*(m-1);j++)
if (y[j]<m)
for (int k=1;k<=m-y[j];k++)
if (y[j]+k<y[j+x[i-1]*k]) y[j+x[i-1]*k]=y[j]+k;
while (y[r]<maxint) r++;
转载的那篇博文对这个有更深入的分析。
速度有明显的提高。
下面是按照这种方法做的代码:
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define INF 2147483647
#define MAXN 2000
using namespace std;
int h, k;
int ans[MAXN], maxStampVal, stampVal[MAXN], maxVal[MAXN], y[MAXN];
bool occur[MAXN];
void search(int cur){
if(cur >= k){
if(maxVal[cur-1] > maxStampVal){
maxStampVal = maxVal[cur-1];
memcpy(ans, stampVal, sizeof(stampVal));
}
return ;
}
int tmp[MAXN];
memcpy(tmp, y, sizeof(y));
for(int i=stampVal[cur-1]+1; i<=maxVal[cur-1]+1; ++i){
stampVal[cur] = i;
// 关键步骤,利用了动态规划的思想
for(int j=0; j<stampVal[cur-1]*h; ++j)if(y[j]<h){
for(int num=1; num<=h-y[j]; ++num){
if(y[j]+num < y[j + i*num] && (j+i*num<MAXN))
y[j+i*num] = y[j]+num;
}
}
int r = maxVal[cur-1];
while(y[r+1]<INF) r++;
maxVal[cur] = r;
search(cur+1);
memcpy(y, tmp, sizeof(tmp));
}
}
int main(){
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
// h数量, k面额数
while(scanf("%d %d", &h, &k), h+k){
stampVal[0] = 1;
maxVal[0] = h;
int i;
for(i=0; i<=h; ++i)
y[i] = i;
while(i<MAXN) y[i++] = INF;
maxStampVal = -2147483645;
search(1);
for(i=0; i<k; ++i)
printf("%3d", ans[i]);
printf(" ->%3d\n", maxStampVal);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
北大ACM-POJ1010 - STAMPS 原比赛(Pacific Northwest 1998)题目的测试数据
北大POJ1010-STAMPS 解题报告+AC代码
很好的儿童涂鸦开源软件的图章资源tuxpaint-stamps,因为只能上传15M以下的文件,所以分成三个分卷。
针对新汶矿区,采用SBAS-StaMPS方法对2016~2020年48景Sentinel-1A影像进行时序分析,反演了4年的地表形变过程,提取了8个采煤区地表时序沉降量,最大沉降量达180 mm,最大沉降速率为44.49 mm/a,沉降区中心表现出...
composer require orisintel/laravel-process-stamps 组态 php artisan vendor:publish --provider= "\OrisIntel\ProcessStamps\ProcessStampsServiceProvider" 运行上面的命令将同时发布迁移和配置文件。 用法 在...
StaMPS开源软件4.1版本 带使用手册
caledonian-stamps
合成孔径雷达干涉测量ps-insar软件stamps操作说明书
有用的邮票常用邮票的收藏。
Bravis邮票申请 我的第一个React应用程序是在DigiGarden开放期间人们用来收集邮票的小型应用程序。先决条件为了运行脚本,您需要安装npm和node正在安装git克隆存储库。 运行npm install 运行npm start部署方式部署此...
StaMPS较新的版本,增加了SBAS算法
StaMPS软件操作流程.docx
StaMPS/MTI Manual Version 3.3b1 基于StaMPS的PS时序分析 、SBAS时序分析
stamps hooper v 4.01 pdf
永久性散射体开源软件StaMPS4.1版本详解 教程全套
俄罗斯的邮票 资料库以机器可读的格式包含有关俄罗斯邮票的信息。 邮票图像取自网站 。
基于Snap和StaMPS对Sentinel-1 SLC数据进行PS-InSAR处理