本文主要是介绍POJ 1010 STAMPS 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题大神解释得很清楚，包括我根本没有意识到的优化（同面额的邮票种类大于5的情况解是一样的）。我一开始也是按照递归深搜做的，效果比较差，应该是剪枝的地方没有考虑情况。这道题剪枝同时考虑效率和正确性还是比较难的。后来按照最直观的四重循环做的。因为邮票组合最多四种。
具体分析可以移步大神的解题报告：http://blog.csdn.net/cugbliang/article/details/2742242
代码写得比较繁琐，重复代码比较多。另外，对STL中的vector实现还是不清楚，具体来说就是clear()和resize()在windows下用visual studio 2010 sp1 ultimate环境下运行有时会抛异常，我到后来还是没弄清楚为什么。不过程序在linux下用gcc编译运行是没有问题的。
| 1010 | Accepted | 192K | 32MS |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int N = 100;
int n = 0;
int stamps[N];struct Allocation{int nstamps;int ntypes;int highestvalue;bool tie;vector<int> stamps;Allocation(){nstamps = 0;ntypes = 0;highestvalue = 0;tie = false;stamps.resize(4);}
};vector<Allocation> sols;void updateSolution(const int req, Allocation &allocation, int *type, int cnt)
{if(sols[req].ntypes < allocation.ntypes || sols[req].ntypes == allocation.ntypes && sols[req].nstamps > allocation.nstamps ||sols[req].ntypes == allocation.ntypes && sols[req].nstamps == allocation.nstamps && sols[req].highestvalue < allocation.highestvalue){sols[req] = allocation;sols[req].tie = false;}else if(sols[req].ntypes == allocation.ntypes && sols[req].nstamps == allocation.nstamps&& sols[req].highestvalue == allocation.highestvalue){sols[req].tie = true;}
}void updateAllocation(int &req, Allocation &allocation, int *type, int cnt)
{allocation.nstamps = cnt;allocation.stamps[cnt - 1] = stamps[type[cnt - 1]];if(type[cnt - 1] != type[cnt - 2]){allocation.ntypes++;}allocation.highestvalue = stamps[type[cnt - 1]];
}int main()
{int stamp;while(fscanf(stdin, "%d", &stamp) > 0){memset(stamps, 0, n * sizeof(int));n = 0;int pre = 0;int cnt = 0;while(stamp != 0){if(stamp == pre){cnt++;}else{cnt = 0;}if(cnt < 5){stamps[n] = stamp;n++;}fscanf(stdin, "%d", &stamp);}//sort(stamps, stamps + n);vector<int> reqs;int reqest, maxreq = 0;fscanf(stdin, "%d", &reqest);while(reqest != 0){reqs.push_back(reqest);if(reqest > maxreq){maxreq = reqest;}fscanf(stdin, "%d", &reqest);}int upperbnd = min(stamps[n - 1] * 4, maxreq);if(!sols.empty()){sols.clear();}sols.resize(upperbnd + 1);int type[4], req[4];Allocation allocation[4];for(type[0] = 0; type[0] < n; ++type[0]){req[0] = stamps[type[0]];if(req[0] > upperbnd){break;}allocation[0] = Allocation();allocation[0].nstamps = 1;allocation[0].stamps[0] = stamps[type[0]];allocation[0].ntypes = 1;allocation[0].highestvalue = stamps[type[0]];updateSolution(req[0], allocation[0], type, 1);for(type[1] = type[0]; type[1] < n; ++type[1]){req[1] = req[0];req[1] += stamps[type[1]];if(req[1] > upperbnd){break;}allocation[1] = allocation[0];updateAllocation(req[1], allocation[1], type, 2);updateSolution(req[1], allocation[1], type, 2); for(type[2] = type[1]; type[2] < n; ++type[2]){req[2] = req[1];req[2] += stamps[type[2]];if(req[2] > upperbnd){break;}allocation[2] = allocation[1];updateAllocation(req[2], allocation[2], type, 3);updateSolution(req[2], allocation[2], type, 3);for(type[3] = type[2]; type[3] < n; ++type[3]){req[3] = req[2];req[3] += stamps[type[3]];if(req[3] > upperbnd){break;} allocation[3] = allocation[2];updateAllocation(req[3], allocation[3], type, 4);updateSolution(req[3], allocation[3], type, 4);}}}}for(int i = 0; i < reqs.size(); ++i){int req = reqs[i];fprintf(stdout, "%d ", req);if(req > upperbnd || sols[req].ntypes == 0){fprintf(stdout, "---- none\n");}else{fprintf(stdout, "(%d):", sols[req].ntypes);if(sols[req].tie){fprintf(stdout, " tie\n");}else{for(int j = 0; j < sols[req].nstamps; ++j){fprintf(stdout, " %d", sols[req].stamps[j]);}fprintf(stdout, "\n");}}}}return 0;
}这篇关于POJ 1010 STAMPS 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
