回溯法解组合问题——硬币问题

墨蓝 2022-05-26 12:14 82阅读 0赞

问题：

1，你有（足够的）5分，2分，1分的硬币，现在要凑出来12分的结果，那么最少的硬币组合是？

2，如果有5,12,7，-5，-7，-12这六个硬币。现在要你凑0-2000以内的任意数又该如何组合呢？

用回溯法解组合问题。在解空间中搜索。

// MoneyCount.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <time.h>
    using namespace std;
    
    vector<int> MoneyKind;
    int Total=0;
    vector<int> bestSolution; //最优解
    int flag=0;			//用来判断是否第一次找到可行解
    //solution 存有问题的当前解
    //total 目前还是需要多少
    //x 为增加哪一个硬币
    void FindSolution( vector<int> & solution, int total, int x )
    {
    	if( total == x ) //找到了一个可行解
    	{
    		if( flag == 0 )
    		{
    			bestSolution = solution;
    			flag = 1;
    		}
    		else
    		{
    			if( solution.size() < bestSolution.size() )
    				bestSolution = solution;
    		}
    		return;
    	}
    
    	//搜索每一个子节点
    	total = total - x;
    	
    	for( int i=0; i<(int)MoneyKind.size(); i++ )
    	{
    		solution.push_back( MoneyKind[i] );
    		if( MoneyKind[i]<=total )			//可行性约束
    		{
    			if( flag==1 && solution.size() <= bestSolution.size() )
    				FindSolution( solution, total ,MoneyKind[i] ); 
    			if( flag==0)                                //没有找到可行解
    				FindSolution( solution, total ,MoneyKind[i] );
    		}
    		solution.pop_back();
    	}
    	
    }
    
    void input()
    {
    	int numKinds=0;
    	cout << "How many kinds of coins?\n";
    	cin >> numKinds;
    	//MoneyKind.resize( numKinds );
    	cout << "Input all kinds of coins:\n";
    	for( int i=0; i<numKinds; i++)
    	{
    		int m=0;
    		cin >> m;
    		MoneyKind.push_back(m);
    	}
    //	sort(MoneyKind.begin(), MoneyKind.end());
    	cout << "Input the total money of coins:\n";
    	cin >> Total;
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	input();
    	clock_t begin = clock();
    	vector<int> solution;
    	for( int i=0; i<(int)MoneyKind.size(); i++ )
    	{
    		solution.push_back( MoneyKind[i] );
    		if( MoneyKind[i]<=Total )			//可行性约束
    		{
    			if( flag==1 && solution.size() <= bestSolution.size() )
    				FindSolution( solution, Total ,MoneyKind[i] ); 
    			if( flag==0 )                                //没有找到可行解
    				FindSolution( solution, Total ,MoneyKind[i] );
    		}
    		solution.pop_back();
    	}
    
    	if( flag == 0 )
    		cout << "NO SOLUTION!" <<endl;
    	else
    	{
    		cout << "SOLUTION IS:\n" ;
    		sort( bestSolution.begin(),bestSolution.end() );
    		for( int i=0; i<(int)bestSolution.size(); i++)
    			cout << bestSolution[i] << " ";
    		cout <<"\nTime used "<< (clock()-begin)/1000.0 << "s" <<endl;
    	}
    
    	return 0;
    }