题目：
小明同学，在参加1场考试，考试时间是两个小时，试卷上一共有n道题目，小明要在规定的时间内完成一定数量的题目；
考试中不限制试题作答顺序，对于第i道题目，小明有三种不同的策略进行选择：
（1）直接跳过这道题目不花费时间，本题得0分；
（2）只做一部分题目，花费pi分钟的时间，本题可以得到ai分；
（3）做完整个题目花费qi分钟的时间，可以得到bi分；
小明想知道他最多能得到多少分？
输入：
第一行输入一个n数表示题目的数量
接下来n行 ，每行四个数表示pi，ai，qi，bi（1<=n<=100,1<=pi<=qi<=120,0<=ai<=bi<1000）；
输出：
输出一个整数，小明的最高分。
样例输入：
4
20 20 100 60
50 30 80 55
100 50 110 88
5 3 10 6
样例输出:
94
思路：
稍微复杂点的背包问题；
实现：
1 #include <bits/stdc++.h>
2 using namespace std;
3 int TIME =
121;
4 int process(
const vector<
int>& p,
const vector<
int>&
a,
5 const vector<
int>& q,
const vector<
int>&
b) {
6 int n =
p.size();
7 if (n ==
0)
return 0;
8
9 vector<vector<
int> > memo(n,vector<
int>(TIME+
1,-
1));
10 for (
int j =
0; j <= TIME; ++
j) {
11 memo[
0][j] = (j >= p[
0] ? a[
0]:
0);
12 memo[
0][j] = (j >= q[
0] && b[
0] > a[
0] ? b[
0]:memo[
0][j]);
13 }
14
15 for (
int i =
1; i < n; ++
i) {
16 for (
int j =
0; j <= TIME ; ++
j) {
17 memo[i][j] = memo[i-
1][j];
18 if (j >=
p[i])
19 memo[i][j] = max(memo[i][j],a[i] + memo[i-
1][j-
p[i]]);
20 if (j >=
q[i]) {
21 memo[i][j] = max(memo[i][j],b[i] + memo[i-
1][j-
q[i]]);
22 }
23 }
24 }
25
26 return memo[n-
1][TIME];
27 }
28
29
30 int main()
31 {
32 int n;
33 cin >>
n;
34 int dp[TIME];
35 memset(dp,
0, TIME *
sizeof(
int));
36 int p, a, q, b;
37
38 vector<
int>
pVector;
39 vector<
int>
aVector;
40 vector<
int>
qVector;
41 vector<
int>
bVector;
42
43 for (
int k =
0; k < n; ++
k) {
44 cin >> p >> a >> q >>
b;
45 pVector.push_back(p);
46 aVector.push_back(a);
47 qVector.push_back(q);
48 bVector.push_back(b);
49 }
50 cout <<
process(pVector,aVector,qVector,bVector);
51 }
-------64%解法-，留作参考---------------------------
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int TIME =
121;
5
6 int main()
7 {
8 int n;
9 cin >>
n;
10 int dp[TIME];
11 memset(dp,
0, TIME *
sizeof(
int));
12 int p, a, q, b;
13 int i, j;
14 for (i =
0; i < n; i++
)
15 {
16 cin >> p >> a >> q >>
b;
17 for (j =
0; j + p < TIME; j++
)
18 {
19 dp[j] = max(dp[j], dp[j + p] +
a);
20 }
21 for (j =
0; j + q < TIME; j++
)
22 {
23 dp[j] = max(dp[j], dp[j + q] +
b);
24 }
25 }
26 int ret =
0;
27 for (i =
0; i < TIME; i++
)
28 {
29 ret =
max(ret, dp[i]);
30 }
31 cout <<
ret;
32 }
转载于:https://www.cnblogs.com/TonvyLeeBlogs/p/9601339.html
