贪心算法之纸币问题

深藏阁楼爱情的钟 2022-11-25 04:14 236阅读 0赞

纸币问题相信大家很熟悉了  
这里提出一个问题：  
设：有1，5，11这三种纸币，每种纸币**足够多**，问：至少需要多少张纸币才能凑够136元呢  
动起笔，写写画画，最后得出的结论是14张纸币  
11张11元  
3张5元  
我快速过一遍基本的纸币问题代码

#include<iostream>
    #include<cmath>
    using namespace std;
    int main()
    { 
    	int money,n=0;
    	cin>>money;
    	int a[3]={ 1,5,11};//三种纸币的面值
    	int dp[3]={ 500,500,500};//保证足够多
    	for(int i=2;i>=0;i--)//从大凑到小
    	{ 
    		int c=min(money/a[i],dp[i]);//求最小值...
    		money-=a[i]*c;
    		n+=c;
    	}
    	cout<<n<<"\n";
        return 0;
    }

那么运行后输入136，得出的居然是16！  
12张11元  
4张1元  
由此可见，贪心并不是最优解，而是局部的最优解  
个人思维：

如果136元
    我拿1张11元，然后拿25张5元，共26张放进数组中
    我拿2张11元，然后拿22张5元，再拿4张1元，共28张放入数组中
    我拿3张11元，然后拿20张5元，再拿3张1元，共26张放入数组中
    。。。。later
    我拿11张11元，然后拿3张5元，共14张放入数组中
    我拿12张11元，然后拿4张1元，共16张放入数组中
    最后结果，14张为最小

上代码！

#include<iostream>
    using namespace std;
    int main()
    { 
    	int n,min=9999,sum=0,m,a[1000]={ 0},len=0;
    	cin>>n;
    	m=n;
    	if(n%5==0) 
    	{ 
    		a[len]=n/5; len++;
    	}
    	else if(n%11==0) 
    	{ 
    		a[len]=n/11; len++;
    	}
    	for(int i=1;i<=m/11;i++)
    	{ 
    		sum=0;
    		sum+=i;
    		m-=11*i;
    		for(int j=1;j<=m/5;j++)
    		{ 
    			sum+=j;
    			m-=5*j;
    		}
    		sum+=m;	
    		a[len+i]=sum;
    		m=n; 
    	}	
    	for(int i=0;i<100;i++) if(a[i]<min&&a[i]!=0) min=a[i];
    	cout<<min;
    	return 0;
    }

输入136，输出14
    输入15，输出3
    输入2345，输出235

我是奋斗的小牛，一个一直在信息时代奋斗的牛，专注C/C++/Java/其他类的菜鸟/中级类问题和其他问题  
喜欢的，加个关注！