本文主要是介绍PAT1068 Find More Coins (30)（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出n枚钱币，要求买价值为m的物品，要求输出具体所用的钱币，如有多种情况输出字典序最小的情况。
思路：
这题就是01背包的变种，状态转移方程很好写：dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+c[i])
主要难点在于怎么处理多种情况最后输出，基本思路是一开始将钱币按从大到小排序，在状态转移的过程中用hash[i][j]保存是否选取了当前钱币i，这样最后对dp[n][m]倒序输出时会优先输出币值小的从而符合字典序。
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
const int maxn = 10050;
int num[maxn], dp[maxn][150];
int pos[maxn][150];int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &num[i]);sort(num+1, num + n+1, greater<int>());for (int i = 1; i <= n; i++) {for (int j = num[i]; j <= m; j++) {if (dp[i - 1][j] <= dp[i-1][j - num[i]] + num[i]) {dp[i][j] = dp[i-1][j - num[i]] + num[i];pos[i][j] = 1;} else {dp[i][j] = dp[i - 1][j];pos[i][j] = 0;}}} if (dp[n][m] != m)printf("No Solution\n");else {vector<int> res;int road = m,index=n;while (road > 0) {if (pos[index][road]==1) {res.push_back(num[index]);road -= num[index];}index--;}for (int i = 0; i<res.size(); i++) {if (i == 0)printf("%d", res[i]);elseprintf(" %d", res[i]);}} return 0;
}这篇关于PAT1068 Find More Coins (30)（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
