杀死恶龙II(dragon)DP

Question

杀死恶龙II(dragon)
问题描述：
王国里又来了一头恶龙，国王又到骑士工会征集n名骑士去杀死这条恶龙。假定这条恶龙的生命值为H，而每位骑士有攻击力ai，他可以砍伤恶龙ai点生命值，他所得的报酬就是他的攻击力。请你帮助国王计算，如果要杀死这个恶龙，也就是把恶龙的生命值全部消灭，他最少要支付多少报酬（注意：不一定要求这n名骑士都去攻击，只需要选择部分骑士即可完成任务，此时国王只需要支付参与攻击的那部分骑士即可）。
输入格式：
第一行为正整数n(≤100)和H(≤106)；第二行为n个正整数ai(≤105)，分别表示每位骑士的攻击力。
输出格式：
输出仅一个整数，表示国王必须支付的最低代价，如果不能杀死恶龙，输出-1。
输入样例
5 16
3 1 3 5 6
输出样例
17

Answer 1

这是一道典型的背包问题。在这道题中，我们可以将每位骑士看作是一种物品，攻击力ai看作是价值，他自己的价格看作是他的攻击力。我们的目标是尽可能使用少的骑士来消灭恶龙，并且让国王支付的报酬最少。

为了解决这道题，我们可以使用01背包算法来求解。首先，我们可以使用一个一维数组f[i]表示当恶龙的生命值为i时，国王支付的最低代价。然后，我们可以枚举每位骑士，分别计算出使用这位骑士可以让国王支付的最低代价。

具体来说，我们可以使用以下代码来实现：

for (int i = 0; i < n; i++) {
  for (int j = h; j >= a[i]; j--) {
    f[j] = min(f[j], f[j - a[i]] + a[i]);
  }
}

在上面的代码中，我们首先使用枚举骑士的循环来遍历每位骑士。然后，我们使用双重循环来枚举恶龙的生命值j。在循环中，我们可以使用 f[j] = min(f[j], f[j - a[i]] + a[i]) 语句来更新状态。在这个语句中，f[j] 表示当前的最低代价，f[j - a[i]] 表示使用第i位骑士的情况下的最低代价