第一眼看这道题。。。啊哈，啥？？？
仔细看一看，发现：诶， 这不是01背包吗？
两人水平值的比值*老王做题用时 可以算出WKY做每道题的用时。 那么每道题的p就可以转换成费用c[i], 价值q就是w[i]
这么一来， 这道题就转化成了在一定大小的背包内（即规定时间内）可以装下的最大价值的物品， 这样， 就是一道01背包的问题了。
Code
#include <iostream> #include <cstdio> #include <cstring> using namespace std; //Benjamin // int dp[100010]; int n, m, v; int c[100010], w[100010]; int a[100010]; int p1, p2, b; int main() { scanf("%d%d", &p1, &p2); b = p2 / p1;//水平值的倍数 scanf("%d%d", &m, &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); a[i] *= b;//计算出WKY做每道题的时间 } for(int i = 1; i <= m; i++) { scanf("%d%d", &c[i], &w[i]); c[i] = a[c[i]]; } scanf("%d", &v); //01背包 for(int i = 1; i <= m; i++) { for(int j = v; j >= c[i]; j--) { dp[j] = max(dp[j], dp[j-c[i]] + w[i]); } } printf("%d\n", dp[v]); return 0; }
原文：https://www.cnblogs.com/Benjamin-cpp/p/10371729.html