本文主要是介绍北大OJ_1010题：STAMPS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;typedef vector<int> IntArray;#define MAX_STAMP_N 4 //最大邮票数
#define MAX_TYPE_N 25 //最大邮票种类数25struct tagResultHelper
{int nCurTypeCount; //当前种类数int nCurStampCount; //当前邮票数int nCurMaxValue; //当前最大面额int mResultSets[MAX_STAMP_N]; //当前结果集（始终保存最优的结果集）bool bTieFlag; //tie标记
};tagResultHelper gResultHelper; //结果集合辅助变量
int gStampArray[MAX_TYPE_N]; //邮票种类数组（保存每种面值）
int gTotalTypeCount; //总的邮票种类数//得到最大值
int GetMaxValue( int mIntArray[MAX_STAMP_N], int nCurCount )
{int nMax = -1;for( int i = 0; i < nCurCount; ++i ){if ( mIntArray[i] > nMax ){nMax = mIntArray[i];}}return nMax;
}//更新最优解
void UpdateBestResult( int nCurTypeCount, int nCurMaxValue, int nCurStampCount,int mIntArray[MAX_STAMP_N] )
{//种类多于当前的，加入if ( nCurTypeCount > gResultHelper.nCurTypeCount ){gResultHelper.nCurTypeCount = nCurTypeCount;gResultHelper.nCurStampCount = nCurStampCount;gResultHelper.nCurMaxValue = nCurMaxValue;//更新结果gResultHelper.bTieFlag = false;//重置tie标记for( int i = 0; i < nCurStampCount; ++i ) gResultHelper.mResultSets[i]=mIntArray[i];}//种类等于当前的else if ( nCurTypeCount == gResultHelper.nCurTypeCount ){//邮票数目小于当前的if( nCurStampCount < gResultHelper.nCurStampCount ){gResultHelper.nCurTypeCount = nCurTypeCount;gResultHelper.nCurStampCount = nCurStampCount;gResultHelper.nCurMaxValue = nCurMaxValue;//更新结果gResultHelper.bTieFlag = false;//重置tie标记for( int i = 0; i < nCurStampCount; ++i ) gResultHelper.mResultSets[i]=mIntArray[i];}//邮票数目等于当前的else if ( nCurStampCount == gResultHelper.nCurStampCount ){//单张面值最大的大于当前的if ( nCurMaxValue > gResultHelper.nCurMaxValue ){gResultHelper.nCurTypeCount = nCurTypeCount;gResultHelper.nCurStampCount = nCurStampCount;gResultHelper.nCurMaxValue = nCurMaxValue;//更新结果gResultHelper.bTieFlag = false;//重置tie标记for( int i = 0; i < nCurStampCount; ++i ) gResultHelper.mResultSets[i]=mIntArray[i];}//单张面值最大的等于当前的else if ( nCurMaxValue == gResultHelper.nCurMaxValue ){if ( !gResultHelper.bTieFlag ){for( int i = 0; i < nCurStampCount; ++i ) gResultHelper.mResultSets[i]=mIntArray[i];gResultHelper.bTieFlag = true;//已经tie了}}}}
}void GetResult_DFS( int mDstArrayTemp[], int& nCurStampCount, int& nCurTypeCount, int nTarget, int iStart )
{if ( nTarget < 0 ) return;if ( nTarget == 0 ){//找到一组结果UpdateBestResult( nCurTypeCount, GetMaxValue( mDstArrayTemp, nCurStampCount ), nCurStampCount, mDstArrayTemp );}else{for( int i = iStart; i < gTotalTypeCount; ++i ){//后面更大的数不可能满足条件或者邮票数已经是4张，不能容纳更多了（剪枝操作）if( gStampArray[i] > nTarget || nCurStampCount >= 4 ) break;//种类数递增if ( i > iStart || nCurStampCount <= 0 ){++nCurTypeCount;}mDstArrayTemp[nCurStampCount++] = gStampArray[i];//因为可以重复使用，所以可继续从当前位置递归GetResult_DFS( mDstArrayTemp, nCurStampCount, nCurTypeCount, nTarget-gStampArray[i], i );//重置，即回溯操作if ( i > iStart || nCurStampCount == 1 ){--nCurTypeCount;}nCurStampCount--;}}
}//回溯法
int main()
{IntArray customerVec;while ( true ){int nTemp = 0;int type[MAX_TYPE_N] = {0}; //面值为i的邮票的种数type[i] gTotalTypeCount = 0;//while( cin >> nTemp )while( true ){if ( scanf("%d", &nTemp ) == EOF ) exit(0);if ( 0 == nTemp || gTotalTypeCount == MAX_TYPE_N ) break;//gStampArray[gTotalTypeCount++] = nTemp;if( type[nTemp-1] < 5 ) //剪枝，同面额的邮票种类超过5，则按5计算 { type[nTemp-1]++; gStampArray[gTotalTypeCount++] = nTemp;}}sort( gStampArray, gStampArray+gTotalTypeCount );customerVec.clear();while( cin >> nTemp ){if ( 0 == nTemp ) break;customerVec.push_back( nTemp );}for( int i = 0; i < customerVec.size(); ++i ){int iCurTypeCount = 0;int iCurStampCount = 0;int mDstVecTemp[MAX_STAMP_N];memset( mDstVecTemp, 0, sizeof(mDstVecTemp) );gResultHelper.nCurMaxValue = 0;gResultHelper.nCurStampCount = 0;gResultHelper.nCurTypeCount = 0;gResultHelper.bTieFlag = false;memset( gResultHelper.mResultSets, 0, sizeof(gResultHelper.mResultSets) );GetResult_DFS( mDstVecTemp, iCurStampCount, iCurTypeCount, customerVec[i], 0 );if ( gResultHelper.nCurTypeCount <= 0 ){cout << customerVec[i] << " ---- none" << endl;}else if ( gResultHelper.bTieFlag ){cout << customerVec[i] << " (" << gResultHelper.nCurTypeCount << "): tie" << endl;}else{cout << customerVec[i] << " (" << gResultHelper.nCurTypeCount << "):";for( int k = 0; k < gResultHelper.nCurStampCount; ++k ){cout << " " << gResultHelper.mResultSets[k];}cout << endl;}}}return 0;
}
参考文章：http://blog.csdn.net/lyy289065406/article/details/6647948
作者：山丘儿
转载请标明出处，谢谢。原文地址：http://blog.csdn.net/s634772208/article/details/46726249
这篇关于北大OJ_1010题：STAMPS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
