L3-001 凑零钱 (01背包)
L3-001 凑零钱 (30 分)
韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里,发现这家店有个特别的规矩:你可以用任何星球的硬币付钱,但是绝不找零,当然也不能欠债。韩梅梅手边有 104 枚来自各个星球的硬币,需要请你帮她盘算一下,是否可能精确凑出要付的款额。
输入格式:
输入第一行给出两个正整数:N(≤104)是硬币的总个数,M(≤102)是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。
输出格式:
在一行中输出硬币的面值 V1≤V2≤⋯≤Vk,满足条件 V1+V2+...+Vk=M。数字间以 1 个空格分隔,行首尾不得有多余空格。若解不唯一,则输出最小序列。若无解,则输出 No Solution
。
注:我们说序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”,是指存在 k≥1 使得 A[i]=B[i] 对所有 i<k 成立,并且 A[k]<B[k]。
输入样例 1:
8 9
5 9 8 7 2 3 4 1
输出样例 1:
1 3 5
输入样例 2:
4 8
7 2 4 3
输出样例 2:
No Solution
题意:略
思路:如果不要求输出 最小序列,其实是一个01背包问题,应该都没问题。但题目要求输出最小序列,所以我们的要稍微变换一下。刚开始我是先把n没硬币从小到大排序,然后记录一下得到价值j得时候用的硬币的序号。但是一直不对,当时没有想清楚。后来看别人是从大到小排序的焕然大悟。
从小到大排序时,当我们遍历到后面的时候,后面价值比较大得硬币就有可能把前面价值小的给遮掩住了。而如果我们从大到小的话,那么小的硬币就会遮住大的硬币,而这刚好符合题目的要求:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100 * 100 + 10;
int dp[maxn],a[maxn], vis[maxn],m, n,step[maxn][110];
int nextt[100 + 10];
void print(int s) {
if (nextt[s] == -1)return;
print(s-a[nextt[s]]);
printf("%d ",a[nextt[s]]);
}
bool cmp(int a, int b) { return a > b; }
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
sort(a+1,a+1+n,cmp);
memset(dp,0,sizeof(dp));
memset(step,0,sizeof(step));
memset(nextt,-1,sizeof(nextt));
for (int i = 1; i <= n; i++) {
for (int j = m; j >= a[i]; j--) {
if (dp[j] <= dp[j - a[i]] + a[i]) {
dp[j] = dp[j - a[i]] + a[i];
step[i][j] = 1;
}
}
}
if (dp[m]==m) {
while (n) {
while (step[n][m] == 0)n--;
if (n > 0) {
if (m - a[n])
cout << a[n] << ' ';
else
cout << a[n] << endl;
m -= a[n];
}
if (m <= 0)break;
n--;
}
}
else
cout << "No Solution" << endl;
return 0;
}