p2669 [noip2015 普及组] 金币

题目描述

有 n 个金矿，第 i 个金矿可开采出金子的数量为 g[i]，需要的工人数为 p[i]。有 m 个工人，每个工人只能开采一个金矿，每个金矿最多只能开采一次。

现在需要你编写一个程序，计算出在不超过 m 个工人的情况下，最多可以获得多少金子。

输入格式
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示每个金矿可开采出的金子数量 g[i]。

第三行包含 n 个整数，表示每个金矿需要的工人数 p[i]。

输出格式
输出一个整数，表示在不超过 m 个工人的情况下，最多可以获得多少金子。

输入样例
5 10
400 500 200 300 350
5 5 3 4 3

输出样例
900

数据范围
1≤n≤1000,1≤m≤10000,0≤g[i],p[i]≤1000

解题思路：

采用动态规划的方式解决。定义状态f(i,j)表示对前i个金矿，用j个工人最多可获得的金子数。
则转移方程为f(i,j)=max{f(i-1,j),f(i-1,j-p[i])+g[i]}
其中f(i-1,j)表示不选择第i个金矿，f(i-1,j-p[i])+g[i]表示选择第i个金矿。
边界条件为f(i,0)=0,f(0,j)=0。
最终答案为f(n,m)。

时间复杂度分析：
共有n*m个状态，每个状态都需要进行一次状态转移，则总时间复杂度为O(nm)。

参考代码：