【HDU3348】coins(贪心,动态规划DP)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 12 日

"Yakexi, this is the best age!" Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao)
"Thanks to the best age, I can buy many things!" Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn't like to get the change, that is, he will give the bookseller exactly P Jiao.
题意:给出5中币值的钱的数量,让找出一定钱数的最少和最多币值数量的方案的币值数是多少。
题解:发现五种币值是可以约分的,没有互质的,所以简单贪心即可,当时做的时候没有感觉出或者是证明出贪心策略的正确性,所以就想用动态规划背包背,结果就TL,想来用物品的二进制优化应该可以过吧,不过已经写好的代码改起来太麻烦了,就没有改了。。。有空看看吧。。。

#include <iostream>
using namespace std;
int w[6] = {1,5,10,50,100},num[5],use[5];
bool dfs(int v,int x){
	if (x < 0)
		return false;
	int n = v / w[x];
	if (num[x] >= n){
		num[x] -= n;
		use[x] += n;
		return true;
	}
	if (dfs(v - num[x]*w[x],x-1)){
		use[x] += num[x];
		num[x] = 0;
		return true;
	}
	else
		return false;
}
int main(){
	int n,m;
	cin >> n;
	while (n--){
		cin >> m;
		for (int i = 0;i <= 4;i++)
			cin >> num[i];
		int x = m,ans1 = 0,ans2 = 0;
		for (int i = 4;i >= 0;i--){
			use[i] = min(num[i],x / w[i]);
			ans1 += use[i];
			x -= use[i] * w[i];
			num[i] -= use[i];
		}
		if (x){
			cout << "-1 -1" << endl;
			continue;
		}
		for (int i = 4;i >= 0;i--){
			while (use[i]){
				if (dfs(w[i],i-1)){
					use[i]--;
					num[i]++;
				}
				else
					break;
			}
			ans2 += use[i];
		}
		cout << ans1 << ' ' << ans2 << endl;
	}
}
#include <iostream>
using namespace std;
int f[2000005];
int a[6];
int jiazhi[6]={0,1,5,10,50,100};
int main(){
	freopen("1.txt","r",stdin);
	int n,p;
	cin>>n;
	while(n--){
		for (int i=1;i<=1000005;i++)
			f[i]=-0x7fffff;
		f[0]=0;
		cin>>p;
		for (int i=1;i<=5;i++)
			cin>>a[i];
		int res=0,sum=0;
		for (int i=5;i>=1;i--){
			if(sum+jiazhi[i]<=p)
			for (int k=1;k<=a[i];k++){
				if(sum+jiazhi[i]<=p){
					sum+=jiazhi[i];
					res++;
				}
			}
		}
		if(sum!=p){cout<<"-1 -1"<<endl;continue;}
		int lastone=0;
		for(int i=1;i<=5;i++){
			if(lastone<p && a[i]>0){
				for (int j=lastone;j>=0;j--){
					if(f[j]>=0 && f[p]<0){
						for (int k=1;k<=a[i];k++)
							f[j+k*jiazhi[i]]=f[j]+k;
					}
				}
				lastone +=jiazhi[i]*a[i];
			}
		}
		cout<<res<<" "<<f[p]<<endl;
	}
}
个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日