背包问题（帮我结一下）

Question

鲁迅不抓蟋蟀了，他去三味书屋学习了。

现在寿镜吾要读N分钟书，鲁迅想和小伙伴们偷偷出去玩。

想玩A件事，每件需要a[i]分钟且必须完成，每件有b[i]点的开心值。

假设寿镜吾在读书时不会发现，且初始开心值为0，问在不被发现的情况下能达到最大的开心值是多少？

输入格式
第一行输入整数N，A
接下来2 -——（A+1）行，每行两个整数，表示一件事需要的时间和可以得到的开心值

输出格式
输出一个数S，最大开心值。

样例组
输入#1
100 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
输出#1
55
提示说明
样例解释：每件事做完就行了
2<=N,A<=10000，且a[i]和b[i]<=10000

求会的人解题

Answer 1

这个问题是一个经典的贪心算法问题，我们可以通过以下步骤解决：

1. 将所有事情按照所需时间a[i]进行排序。
2. 从头开始累加每件事情的开心值b[i]，直到总时间超过N分钟。
3. 在不超过N分钟的前提下，累加尽可能多的高开心值事情。
   下面是一个可能的解题步骤的伪代码：
   ```
   输入：N, A, a[], b[]
   输出：S
4. 对数组a[]进行排序，同时将对应的b[]也进行排序
5. 初始化总时间T为0，开心值总和S为0
6. 对于i从0到A-1：
   a. 如果T+a[i] <= N，则T = T + a[i]，S = S + b[i]
   b. 否则，跳出循环
7. 输出S
   ```
   根据这个伪代码，我们可以编写程序来解决这个问题。由于问题的规模不大，可以用简单的排序算法，比如快速排序，来对数组进行排序。然后依次累加每件事情的时间和开心值，直到总时间超过N分钟。
   这个问题实际上是一个贪心算法问题，因为我们在每一步都选择了当前情况下最优的解（即开心值最大的事情）。贪心算法在这种问题中通常能够得到最优解，但是这需要通过数学证明或实验验证。在这个问题中，贪心算法的正确性是显然的，因为做更多的事情总是好的，只要不被发现。
   根据样例输入和输出，我们可以看到，在100分钟内，鲁迅可以完成10件事情，而最大的开心值是55。这表明，在前10分钟内，鲁迅应该选择每分钟开心值最大化的事情来做。
   还望采纳