问题描述

邮票问题

设有已知面额的邮票m种,每种有n张,问用总数不超过n张的邮票进行组合,能组合的邮票面额中可以连续的面额数最多有多少?

例如:n=4 m=3

面额分别为:v1=1 v2=2 v3=4

最后的解为14。

请设计回溯算法求解以上问题,分析算法的时间复杂度;利用C语言实现,要求结果正确。

问题分析

首先要读懂题意:即给的邮票能组合成最大的连续数字是多少。

我们不妨假设它可以组合成连续的正无穷的数字。接下来,我们从1数字开始尝试看所给邮票能不能组合而成,显然这是一个for循环。如果一旦不能组合而成,则返回数字减1,即为最大所能组合而成的邮票最大值。

算法设计

首先从文件里读出邮票种类以及其面值、可用邮票数量。

接下来,我们设置一个没有边界的循环,目的是探究最大连续数字是多少

之后利用回溯方法:

尝试每次所选的票的面值,目的是使所有票面值之和为外层假设的最大票数。

部分解:如果加入该票后,总的票的面额没有大于外层假设的最大票数。如果不是,则需要进一步循环尝试

合法解:如果在该票为部分解的前提下,总的票的面额没有大于外层假设的等于票数,此时跳出双重while的回溯算法,继续增加外层假设的最大票数面值之和。

当使用回溯法时,发现对于某个连续的最大票数面值之和没有找到合法解,则该最大票数面值之和减一即为最大连续票数面值之和。

时间复杂度:

两个while回溯循环T= O(n^n)

再加上最外层for循环T = On\^(n+1))= O(n^n)

参考代码

#include <bits/stdc++.h>
using namespace std;


int main()
{
char buffer[220];
ifstream in("Temp.txt");
int m = 0 , n = 0;
in.getline(buffer,20);
sscanf(buffer,"%d%d",&m,&n);
//邮票价值从小输入
vector<int> v(m+1);
int max_value = 0 ;
for(int i = 1 ; i < v.size() ; ++i){
in.getline(buffer,20);
int temp = 0;
sscanf(buffer,"%d",&temp);
v[i] = temp;
if(max_value < temp){max_value = temp;}
}
vector<int> c(n+1);
for(int i = 1 ; ; ++i){
bool flag = false;
for(int k = 1 ; k<=n ; ++k){
c[k] = 0 ;
}
int k = 1 ;
while(k >= 1){
while(c[k] < max_value && k<= n){
for(int j = 1 ; j < v.size() ; ++j) {if(v[j] > c[k]) {c[k] = v[j]; break;}}
int sum = 0 ;
for(int a = 1 ;a < c.size() ; ++a) {sum += c[a];}
//cout << sum<<i << " ";
if(sum == i) {flag = true ;break;}
else if(sum < i) {k += 1 ;}
}
if(flag) {break;}
c[k] = 0 ;
k -= 1 ;
}

if(flag) {continue;}
else {--i;cout << i ; break;}
}
return 0;
}

谢谢访问