hihocode 184

算法 hihocode

描述
最近天气炎热，小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

看题目，DP的问题，具体解法没有很好的思路，最后看到别人的代码，很有启发，记录一下。

其实题目中仔细分析一下，X <= 100, Ai <= 100，因此最终结果最大值为200，这样的话，大大简化了计算复杂度。
可以写出如下代码：

const int N = 202; //输出最高为200
using namespace std;
int main()
{
    int n, x, k;
    int A[N]; //记录本（下标记录金额）
    cin >> n >> x;
    A[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        cin >> k;
        for (int j = N - 1; j >= k; --j) if (A[j - k]) A[j] = 1;
    }
    int i;
    for (i = x; x < N && A[i] == 0; ++i);
    if (i == N) cout << -1 << endl;
    else cout << i << endl;
    return 0;
}

A[i]是一个累加记录的数组，记录所有满足条件的值，最终从x开始向上查找，找到距离x最近的记录值，即为最终结果。很巧妙的方法。