描述
最近天气炎热，小Ho天天宅在家里叫外卖。他常吃的一家餐馆一共有N道菜品，价格分别是A1, A2, ... AN元。并且如果消费总计满X元，还能享受优惠。小Ho是一个不薅羊毛不舒服斯基的人，他希望选择若干道不同的菜品，使得总价在不低于X元的同时尽量低。
你能算出这一餐小Ho最少消费多少元吗？
输入
第一行包含两个整数N和X，(1 <= N <= 20, 1 <= X <= 100)
第二行包含N个整数A1, A2, ...， AN。(1 <= Ai <= 100)
输出
输出最少的消费。如果小Ho把N道菜都买了还不能达到X元的优惠标准，输出-1。
样例输入
10 50
9 9 9 9 9 9 9 9 9 8
样例输出
53
题解：
其实我真的想说这题好™难啊，刚看以为挺简单，最后wa了俩小时，= =
我是这么想的，首先从x枚举到sum，用dp写个ok(u)函数，判断是否可以正好加到u，ok()里面我套的01背包模板，这才是对的，我之前用二分写的，无限wa……
代码：
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int INF = 0x3f3f3f3f;
#define PU puts("");
#define PI(A) cout<<(A)<<endl
#define SI(N) cin>>(N)
#define SII(N,M) cin>>(N)>>(M)
#define cle(a,val) memset(a,(val),sizeof(a))
#define rep(i,b) for(int i=0;i<(b);i++)const int MAXN = 20 + 9 ;
int dp[20 * 100 + 5];
int a[MAXN];
int N, X;bool ok(int u) {for(int i = 0; i < N; i++)for(int j = u; j >= a[i]; j--)dp[j] = max(dp[j], dp[j - a[i]] + a[i]);if(dp[u] == u) return 1;else return 0;
}int main() {while(SII(N, X)) {int sum = 0;rep(i, N) SI(a[i]), sum += a[i];sort(a, a + N);if(sum < X) {puts("-1");continue;}int u = X;for(; u < sum ; u++) {cle(dp, 0);if(ok(u)) break;}PI(u);}return 0;
}以下还有一份，是dfs的代码，写起来很简洁，但时间复杂度就有些高了，O(2^20)
代码2：
#include <bits/stdc++.h>
using namespace std;int min_sum, x;
vector<int> a;void DFS(int idx, int sum) {if(sum >= x) {min_sum = min(sum, min_sum);return;}if(idx >= a.size()) {return;}DFS(idx + 1, sum);DFS(idx + 1, sum + a[idx]);
}int main() {int n;while(scanf("%d %d", &n, &x) != EOF) {a.clear();int temp, sum = 0;for(int i = 0; i < n; ++i) {scanf("%d", &temp);a.push_back(temp);sum += temp;}min_sum = sum;DFS(0, 0);if(min_sum == sum) {printf("-1\n");} else {printf("%d\n", min_sum);}}
}再来一份，大神代码，rank1的，用的是非递归版的，也就是枚举所有情况，复杂度O(2^N)，虽然这份跑的时间比上一份还长，但大神做的时候一定是已经想到了这个复杂度，觉对不会TLE，所以才写的，所以还是比较佩服这份
代码3：
#include <bits/stdc++.h>
using namespace std;#define N 100020
#define M 100200
#define eps 1e-12
#define inf 0x3f3f3f3fint n, a[N], X;
int main() {scanf("%d%d", &n, &X);int sum = 0;for(int i = 0; i < n; ++i) {scanf("%d", &a[i]);sum += a[i];}if(sum < X) {puts("-1");return 0;}int ans = inf;for(int s = 1; s < (1 << n); ++s) {int t = 0;for(int j = 0; j < n; ++j) {if(s >> j & 1) {t += a[j];}}if(t >= X) ans = min(ans, t);}printf("%d\n", ans);return 0;
}
