[数据结构与算法]1068 Find More Coins (30 分)

1068 Find More Coins (30 分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<int> ans;
int dp[10010], v[10010], vis[10010][110]; 
int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		cin >> v[i];
	sort(v, v + n, greater<int>());
	for(int i = 0; i < n; ++i){
		for(int j = m; j >= v[i]; j--){
			if(dp[j] <= dp[j - v[i]] + v[i]){
				dp[j] = dp[j - v[i]] + v[i];
				vis[i][j] = 1; 
			}
		}
	}
	if(dp[m] != m)
		cout << "No Solution";
	else{
		int i = n;
		while(m > 0){
			if(vis[i][m]){
				ans.push_back(v[i]);
				m -= v[i];
			}
			i--;
		}
		for(int i = 0; i < ans.size(); ++i)
			cout << ans[i] << " \n"[i == ans.size() - 1];
	}
}