题目链接
https://www.patest.cn/contests/gplt/L3-001
思路 DP【I】【J】 I 表示第几个物品 J 表示多少钱 dp[i][j] 为 bool 值 表示 当前状态是否能满足 对于一个物品 有两个选择 一个是选 当 arr[i] < j 的时候 dp[i - 1][j - arr[i]] == 1 就可以选 一个是不选 就是 更新为 dp[i - 1][j] 的答案
然后最后找 满足条件的最小序列 在刚开始选的时候 将数组 按 从大到小 排列 然后最后找的时候 从小的开始搜 往大的地方搜 因为 当一个数尽量小 那么这个可解序列 的字典序 就小
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-6; const int INF = 0x3f3f3f3f; const int maxn = 1e4 + 5; const int MOD = 1e9 + 7; int arr[maxn], dp[maxn][105]; int n, m; vector <int> v; bool comp(int x, int y) { return x > y; } bool in_range(int x, int y) { if (x >= 0 && x < n && y > 0 && y <= m) return true; return false; } void dfs(int x, int y) { if (in_range(x, y)) { if (x == 0 && y == arr[x]) { v.push_back(arr[x]); return; } if (dp[x - 1][y - arr[x]]) { v.push_back(arr[x]); dfs(x - 1, y - arr[x]); } else dfs(x - 1, y); } else return; } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); sort(arr, arr + n, comp); memset(dp, 0, sizeof(dp)); if (arr[0] <= m) dp[0][arr[0]] = 1; for (int i = 0; i < n; i++) dp[i][0] = 1; for (int i = 1; i < n; i++) { for (int j = 1; j <= m; j++) { if (arr[i] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - arr[i]]); } } if (dp[n - 1][m]) { v.clear(); dfs(n - 1, m); sort (v.begin(), v.end()); vector <int>::iterator it; for (it = v.begin(); it != v.end(); it++) { if (it != v.begin()) printf(" "); cout << (*it); } cout << endl; } else printf("No Solution\n"); }转载于:https://www.cnblogs.com/Dup4/p/9433230.html
相关资源：JAVA上百实例源码以及开源项目