c++求解题越快越好

Question

输入n个正整数和一个正整数h,请你从这n个数中选出若干个数。使它们的和
大于等于h,我们的目的是使选出的数的个数尽可能的少。

如果可以选出这样的数,输出选出的数的个数。如果不能选出这样的数,输
出-1。

例如有5个正整数26271,h等于12,如果选出(1,2,2,7),共4个数。他
们的和等于12,大于等于12;如果选出(6,7),共2个数,他们的和等于13,
也大于等于12。当然还有(1,6,7)、(2,6,7)、(2,2,6,7)等选取方案
都满足要求,可以证明,(6,7)选取方案中具有最少的个数2,故前出2。

c++

Answer 1

引自免费微信小程序：皆我百晓生

为了解决这个问题，我们可以采用动态规划的方法。首先定义一个数组dp，其中dp[i]表示达到目标和i时所需的最少数字个数。然后遍历给定的数字列表，更新dp数组中的值。当遇到当前数字sum时，我们尝试将它添加到之前的和中，如果总和小于等于目标和h，则更新dp[sum + num]的值。最终，我们需要找到第一个大于等于h的dp值对应的索引，这个索引减去初始值（即dp[0]）就是我们需要的答案。如果没有这样的索引，说明无法达到目标和，结果应为-1。

下面是完整的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, h;
    cin >> n >> h;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 初始化dp数组
    vector<int> dp(h + 1, INT_MAX); // INT_MAX代表无法达到的和
    dp[0] = 0; // 当和为0时，不需要任何数字

    // 动态规划过程
    for (int num : nums) {
        for (int i = h; i >= num; --i) { // 从大到小更新dp数组
            if (dp[i - num] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - num] + 1);
            }
        }
    }

    // 查找第一个大于等于h的dp值
    int ans = -1;
    for (int i = h; i <= h; ++i) {
        if (dp[i] != INT_MAX) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;
    return 0;
}

这段代码首先读取输入的n和h，然后读取n个正整数。接下来初始化dp数组，并进行动态规划计算。最后查找第一个大于等于h的dp值并输出结果。注意，在C++中，INT_MAX是整型的最大值，这里用来表示某个和无法达到。