yzm10与大富翁的故事

Description

 

这款《大富翁》游戏曾经是我的启蒙桌游之一,印象最深的就是那一叠叠花花绿绿的钞票,还有和小伙伴从欢乐买地到撕逼掀桌的搞笑回忆~

当你的对手在一整条街上开满了旅馆(经过时要交过路费),每一次掷骰子都会心惊胆战,一不小心就会损失一个亿的感觉(╯▔皿▔)╯。

最近在逛桌游店的时候,我又忍不住上前搓了一把。

yzm10与大富翁的故事.jpg

在购买地产、缴纳地税或交过路费时,往往需要支付一定的金额,我们需要用手中的钞票组合出恰好能支付金额的钱数,满足a[1]+a[2]+...+a[k]=M。

眼下我又来到了死亡一条街...看着小伙伴得意洋洋的样子,我心有不甘地拿出了钞票。

当然了支付时还是有一定技巧的,在选择面值时,尽可能选大额的钞票,这样就可以保证剩下足够多的零钱,有更多的金额组合形式,从而减少了不必要的浪费。这里你只需保证让最小的面值尽可能大即可。

现在告诉你初始时yzm10手里各张钞票的面值,你能猜出他是怎么支付的吗?

Input

 

第一行给出两个正整数:N(1<=N<=10^4)是yzm10手中的钞票数,M(1<=M<=100)是需要支付的金额。

第二行给出N张钞票的非负整数面值(保证在int范围内),数字间以空格分隔。

Output

 

在一行中按升序输出所需支付的各张钞票的面值,保证让最小的面值尽可能大,数字间以空格分隔。

若无法恰好凑出金额(不足或浪费),则输出-1。

Sample Input 1 

4 10
2 3 7 8

Sample Output 1

3 7

Sample Input 2 

5 10
2 3 4 4 5

Sample Output 2

2 4 4

Sample Input 3 

2 10
5 11

Sample Output 3

-1

Hint

答案可能不唯一,本题采用special judge,输出任意一种即可。

 

样例1有两种取法(2,8)(3,7),2<3,选第二种。

样例2有两种取法(2,3,5)(2,4,4),因为最小值都为2,两种均满足条件。

题意:中文题,不解释了,表示暑假训练最后一周没认真做,纳新题出了个输出路径的,一脸懵逼。。。

题解:01背包加输出路径,从大往小装可以保证最小面值最大,因为从大的开始装,所以最后倒着输出,可以保证升序输出,这样就不用排序了。 请看代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX1 = 1e4+10;
const int MAX2 = 200; //数组都开到1e+4+10,会报错(Runtime error)注意这里,很坑!!!
int a[MAX1],dp[MAX2];
int vis[MAX1][MAX2];
bool cmp(int x,int y){
	return x>y;
}
int main(){
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n;i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1,cmp);
	for (int i = 1; i <= n;i++){//01背包模板
		for (int j = m; j >= a[i];j--){
			if(dp[j]<dp[j-a[i]]+a[i]){
				vis[i][j]=1;
				dp[j]=dp[j-a[i]]+a[i];
			}
		}
	}
	if(dp[m]!=m) cout << -1 << endl;
	else{
		int i=n,f=0;
		while(m){//输出路径模板
			if(vis[i][m]){
				if(f==0) f=1;
				else cout << " ";
				cout << a[i];
				m-=a[i];
			}
			i--;
		}
		cout << endl;
	}
	return 0;
}