AcWing 1554. 找更多硬币
原题链接
中等
作者:
fancywing
,
2021-01-20 15:17:46
,
所有人可见
,
阅读 575
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010, M = 110;
int n, m;
int v[N];
int f[N][M];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin>>v[i];
sort(v+1, v+n+1);
memset(f, -0x3f, sizeof f);
f[n + 1][0] = 0;
for(int i = n; i>=1; i--){
for(int j = 0; j <=m; j++){
f[i][j] = f[i+1][j];
if(j>=v[i]) f[i][j] = max(f[i][j], f[i+1][j-v[i]]+v[i]);
}
}
if(f[1][m] < 0) puts("No Solution");
else{
int j = m;
for(int i = 1; i <= n; i++){
if(j >= v[i] && f[i][j] == f[i+1][j-v[i]]+v[i]){
cout<<v[i]<<' ';
j -= v[i];
}
}
}
return 0;
}