首页 > 试题广场 >

考试策略

[编程题]考试策略

热度指数：5013 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小明同学在参加一场考试，考试时间 2 个小时。试卷上一共有 n 道题目，小明要在规定时间内，完成一定数量的题目。考试中不限制试题作答顺序，对于 i 第道题目，小明有三种不同的策略可以选择:

(1)直接跳过这道题目，不花费时间，本题得0分。

(2)只做一部分题目，花费 pi 分钟的时间，本题可以得到 ai 分。

(3)做完整个题目，花费 qi 分钟的时间，本题可以得到 bi 分。

小明想知道，他最多能得到多少分。

数据范围： $1 \le n \le 100 \$ ， $1 \le p_i,q_i \le 120 \$ ， $0 \le a_i \le b_i \le 1000 \$

输入描述:

第一行输入一个n数表示题目的数量。

接下来n行，每行四个数p_i，a_i，q_i，b_i。

输出描述:

输出一个数，小明的最高得分。

示例1

输入

4
20 20 100 60
50 30 80 55
100 60 110 88
5 3 10 6

输出

算法知识视频讲解

C/C++

卷积神经网络哦

01背包问题的简单小变种

简单的01背包问题一维动态规划即可 dp[x]表示容量为x的背包最多能装多少

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5;
int n, p[maxn], a[maxn], q[maxn], b[maxn], dp[125];

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d%d%d%d", &p[i], &a[i], &q[i], &b[i]);
	for(int i = 0; i < n; i++)
		for(int j = 120; j >= 0; j--) {
            if(p[i] <= j)  //考虑这一题全做完
                dp[j] = max(dp[j], dp[j-p[i]] + a[i]);
            if(q[i] <= j)   //考虑这一题只做一半
                dp[j] = max(dp[j], dp[j-q[i]] + b[i]);
        }
    cout<<dp[120]<<endl;
}
/*
4
20 20 100 60
50 30 80 55
100 60 110 88
5 3 10 6

*/

发表于 2019-12-24 12:29:51 回复(0)

pein531

01背包问题，使用动态规划

n = int(input())
dp = [0]*121    # dp[i]表示耗时i分钟时的最高得分
for i in range(n):
    p_i, a_i, q_i, b_i = map(int, input().strip().split())
    for j in range(120, -1, -1):
        if p_i <= j:
            # 第i题全部做完
            dp[j] = max(dp[j], dp[j - p_i] + a_i)     # 比较不做和做完
        if q_i <= j:
            # 第i题只做一部分
            dp[j] = max(dp[j], dp[j - q_i] + b_i)     # 比较不做和做一部分
print(dp[120])

发表于 2021-02-02 15:10:14 回复(0)

Java

LHC0512

Java解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n= Integer.parseInt(scanner.nextLine());
        int[][] record = new int[n][4];
        //接下来n行，每行四个数p_i，a_i，q_i，b_i
        for (int i = 0; i < n; i++) {
            String[] s = scanner.nextLine().split(" ");
            for (int j = 0; j < 4; j++) {
                record[i][j]=Integer.parseInt(s[j]);
            }
        }
        int[] dp=new int[121];
        for(int i = 0; i < n; i++)
            for(int j = 120; j >= 0; j--) {
                if(record[i][0] <= j) dp[j] = Math.max(dp[j], dp[j-record[i][0]] + record[i][1]);
                if(record[i][2] <= j) dp[j] = Math.max(dp[j], dp[j-record[i][2]] + record[i][3]);
            }
        System.out.println(dp[120]);
    }
}

发表于 2020-03-01 21:59:36 回复(1)

正在卷的三文鱼很讨厌吃香菜

典型的01背包问题，物品的迭代在外层循环，费用的迭代在内层循环，注意一下下标

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] p=new int[n+1];
        int[] a=new int[n+1];
        int[] q=new int[n+1];
        int[] b=new int[n+1];
        for(int i=1;i<=n;i++){
            String[] line=br.readLine().split(" ");
            p[i]=Integer.parseInt(line[0]);
            a[i]=Integer.parseInt(line[1]);
            q[i]=Integer.parseInt(line[2]);
            b[i]=Integer.parseInt(line[3]);
        }
        int[][] dp=new int[n+1][121];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=120;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=p[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-p[i]]+a[i]);
                if(j>=q[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-q[i]]+b[i]);
            }
        }
        System.out.println(dp[n][120]);
    }
}

发表于 2019-08-28 19:12:12 回复(0)

Java

柳上原

import java.util.Scanner;

// 考试策略
public class Main {
    /**
     * dp[i][j]   // i门课程用j分钟时的最高得分
     *
     *
     *
     * @param n
     * @param pi
     * @param ai
     * @param qi
     * @param bi
     * @return
     */
    public static int solve(int n, int[] pi, int[] ai, int[] qi, int[] bi){
        int[][] dp = new int[n + 1][121];
        dp[0][0] = 0;
        for (int i=1;i<=n;i++){
            dp[i][0] = 0;
        }

        for (int i=1;i<=120;i++){
            dp[0][i] = 0;
        }

        for (int i=1;i<=n;i++){
            for (int j=1;j<=120;j++){
                int a = dp[i-1][j];
                int b = 0;
                if (j - pi[i-1] >= 0){
                    b = dp[i-1][j-pi[i-1]] + ai[i-1];
                }
                int c = 0;
                if (j - qi[i-1] >= 0){
                    c = dp[i-1][j-qi[i-1]] + bi[i-1];
                }
                dp[i][j] = Math.max(a, Math.max(b, c));
            }
        }

        return dp[n][120];
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] pi = new int[n];
        int[] ai = new int[n];
        int[] qi = new int[n];
        int[] bi = new int[n];
        for (int i=0; i<n; i++){
            pi[i] = scanner.nextInt();
            ai[i] = scanner.nextInt();
            qi[i] = scanner.nextInt();
            bi[i] = scanner.nextInt();
        }


        System.out.println(solve(n, pi, ai, qi, bi));
    }
}

动态规划, 注意输入的意思, 每行分别为pi、ai、qi、bi; 一开始还以为每行依次是p、a、q、b

编辑于 2020-03-18 12:48:54 回复(0)

Endlessstory

def func(l):
    dp =[0 for i in range(121)] #dp[i]表示总时间为i时的最大得分
    for k in l:
        m=120
        while m>= 0:
            if m-k[2]>=0:
                dp[m] =max(dp[m],dp[m-k[2]]+k[3],dp[m-k[0]]+k[1])
            elif m-k[0]>=0:
                dp[m] =max(dp[m],dp[m-k[0]]+k[1])
            m=m-1
    return dp[-1]
if __name__ == '__main__':
    n=int(input())
    l=[]
    for i in range(n):
        l.append(list(map(int,input().strip('\n').split())))
    print(func(l))

编辑于 2019-09-18 22:45:03 回复(1)

C/C++

昔遥暮云

#include <bits/stdc++.h>
//01背包问题
//转移方程：
//①(j>=qi):dp[i][j]=max{dp[i-1][j-qi]+bi , dp[i-1][j-pi]+ai , dp[i][j-1]};
//②(j>=pi):dp[i][j]=max{dp[i-1][j-pi]+ai , dp[i][j-1]};
//③(j<pi):dp[i][j]=dp[i-1][j];
using namespace std;
class test{
public:
    test(){}
    test(int a,int b,int c,int d):pi(a),ai(b),qi(c),bi(d){}
    int pi,ai,qi,bi;
};
int main(){
    int n,dp[100][121]={0};
    cin>>n;
    vector<test> sc(n,test(0,0,0,0));
    for(int i=0;i<n;i++){
        test t;
        cin>>t.pi>>t.ai>>t.qi>>t.bi;
        sc[i]=t;
    }
    for(int j=0;j<=120;j++){
        if(j>=sc[0].qi)
            dp[0][j]=sc[0].bi;
        else if(j>=sc[0].pi)
            dp[0][j]=sc[0].ai;
        else
            dp[0][j]=0;
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=120;j++){
            if(j>=sc[i].qi){
                int pick = max(dp[i-1][j-sc[i].qi]+sc[i].bi , dp[i-1][j-sc[i].pi]+sc[i].ai);
                dp[i][j]=max(pick,dp[i-1][j]);
            }
            else if(j>=sc[i].pi)
                dp[i][j]=max(dp[i-1][j-sc[i].pi]+sc[i].ai,dp[i-1][j]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n-1][120];
    return 0;
}

发表于 2019-09-18 14:58:09 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int v[2][n], w[2][n], dp[121];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
        cin>>v[0][i]>>w[0][i]>>v[1][i]>>w[1][i];

    for(int i=0;i<n;i++)
        for(int j=120;j>=0;j--)
            for(int k=0;k<2;k++)
                if(v[k][i] <= j)
                    dp[j] = max(dp[j], dp[j-v[k][i]]+w[k][i]);
    cout<<dp[120]<<endl;
    return 0;
}

发表于 2019-09-12 03:25:50 回复(0)

算法才是灵魂

典型的01背包
这里需要注意的是，每道题需要用分别保存当前的最优解，再取最大值

from collections import defaultdict
n = int(input())
l = []
for i in range(n):
    tmp = list(map(int, input().split()))
    l.append(tmp)

choose = defaultdict(bool)
dp = [0] * 121
for t1,s1,t2,s2 in l:
    tmp1 = dp[:]
    tmp2 = dp[:]
    for t in range(120, t1-1,-1):
        tmp1[t] = max(tmp1[t], tmp1[t-t1] + s1)
    for t in range(120, t2-1,-1):
        tmp2[t] = max(tmp2[t], tmp2[t-t2] + s2)
    for i in range(1,121):
        dp[i] = max(dp[i], max(tmp1[i],tmp2[i]))
print(dp[120])

编辑于 2019-08-23 21:19:59 回复(0)

花泽类的泪

package main 

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    p := make([]int, n+1)
    q := make([]int, n+1)
    a := make([]int, n+1)
    b := make([]int, n+1)
    dp := make([]int, 121)
    for i := 0; i < n; i++ {
        fmt.Scan(&p[i], &a[i], &q[i], &b[i])        
    }
    for i := 0; i < n; i++ {
        for j := 120; j >= 0; j-- {
            if j-p[i] >= 0 {
                dp[j] = max(dp[j], dp[j-p[i]] + a[i])
            }
            if j-q[i] >= 0 {
                dp[j] = max(dp[j], dp[j-q[i]] + b[i])
            }           
        }
    }
    fmt.Println(dp[120])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

发表于 2022-08-04 20:08:20 回复(0)

Java

May_HanaJung

public class Main{

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
int[] weight = new int[2* total];
int[] value = new int[2 * total];
int index = 0;
sc.nextLine();
for (int i = 0; i < total; i++) {

String[] s = sc.nextLine().split(" ");
weight[index] = Integer.parseInt(s[0]);
value[index] = Integer.parseInt(s[1]);
index += 1;
weight[index] = Integer.parseInt(s[2]);
value[index] = Integer.parseInt(s[3]);
index ++;
}

int maxScore = computeScore(120,weight, value);
System.out.println(maxScore);
}

private static int computeScore(int maxSize,int[] weight,int[] value){
int[] dp = new int[maxSize + 1];

for(int i = 0;i<weight.length;i++){
for(int j = maxSize; j>= weight[i];j--){
dp[j] = Math.max(dp[j-weight[i]]+value[i],dp[j]);
}
}

return dp[maxSize];
}
}

发表于 2021-08-06 21:38:22 回复(0)

牛客763745392号

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

// 0， 1 背包问题的变种


    // 只做一部分，花费p 时间，得a 分，
    // 全做完，花费q 时间，得b分
    int p[101], a[101], q[101], b[101], n;
    
    // dp 表示在120分钟内能得到的最大分值
    int dp[121];

int main()
{
    
    
    
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> p[i] >> a[i] >> q[i] >> b[i];
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 120; j >= 0; j--)
        {
            // 只做一部分
            if(p[i] <= j)
                dp[j] = max(dp[j], dp[j - p[i]] + a[i]);
            
            // 全做完
            if(q[i] <= j)
                dp[j] = max(dp[j], dp[j - q[i]] + b[i]);
        }
    }
    cout << dp[120] << endl;
    
    return 0;
}

我把这部分代码

int p[101], a[101], q[101], b[101], n;
    
    // dp 表示在120分钟内能得到的最大分值
    int dp[121];

放到main里面就过不了，放在main外面就可以过，有没有大神能跟我解释一下为什么，谢谢！

发表于 2021-03-17 15:19:16 回复(0)

simbayx

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> p(n);
    vector<int> a(n);
    vector<int> q(n);
    vector<int> b(n);
    for(int i=0;i<n;i++){
        cin>>p[i]>>a[i]>>q[i]>>b[i];
    }
    vector<vector<int> > dp(121,vector<int>(n+1,0));
    for(int i=1;i<=120;i++){
        for(int j=1;j<=n;j++){
            if(i>=q[j-1])
               dp[i][j]=max(dp[i][j-1],max(dp[i-p[j-1]][j-1]+a[j-1],dp[i-q[j-1]][j-1]+b[j-1]));
            else if(i>=p[j-1]&&i<q[j-1])
                dp[i][j]=max(dp[i][j-1],dp[i-p[j-1]][j-1]+a[j-1]);
            else dp[i][j]=dp[i][j-1];
        }
    }
    cout<<dp[120][n];
    return 0;
}

发表于 2020-09-02 00:18:47 回复(0)

。。刷题

虽然自己还是个菜鸡，刚开始刷动态规划一看题就蒙，慢慢终于自信了，能一次写出来了

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] p = new int[n][2];
        int[][] q = new int[n][2];
        int[] dp = new int[121];
        for(int i=0;i<n;i++){
            p[i][0] = sc.nextInt();
            p[i][1] = sc.nextInt();
            q[i][0] = sc.nextInt();
            q[i][1] = sc.nextInt();
        }
        
        for(int i=0;i<n;i++){
            for(int j=120;j>=1;j--){
                if(j>=p[i][0]&&j>=q[i][0]){
                    dp[j] = Math.max(Math.max(dp[j],dp[j-p[i][0]]+p[i][1]),dp[j-q[i][0]]+q[i][1]);
                }else if(j>=p[i][0]){
                    dp[j] = Math.max(dp[j],dp[j-p[i][0]]+p[i][1]);
                }else if(j>=q[i][0]){
                    dp[j] = Math.max(dp[j],dp[j-q[i][0]]+q[i][1]);
                }
            }
        }
        System.out.println(dp[120]);
    }
}

发表于 2020-06-29 15:09:14 回复(0)

乘号痕😶

n = int(input())
data = [list(map(int, input().split())) for _ in range(n)]
time_limit = 120
dp = [0] * (time_limit + 1)
for i in range(1, n + 1):
    for j in range(time_limit, 0, -1):
        p, a, q, b = data[i - 1]
        if j >= q:
            dp[j] = max(dp[j], dp[j-p] + a, dp[j-q] + b)
        elif j >= p:
            dp[j] = max(dp[j], dp[j-p] + a)
print(dp[-1])

简单01背包

发表于 2019-10-16 18:28:11 回复(0)

那就来一个吧

def have_time_do_this(l):#suppose solutions for subset of item is know
    dp = [0]*121 #from 1 to 120
    for t1,s1,t2,s2 in l:
        m =120
        while m >=0:
            if m>=t2:
                dp[m] = max(dp[m],dp[m-t2]+s2,dp[m-t1]+s1)
            elif m >=t1:
                dp[m] = max(dp[m],dp[m-t1]+s1)
            else:
                break
            m-=1
    return dp[-1]
n = int(input())
l = []
for i in range(n):
    l.append(list(map(int,input().split())))
print(have_time_do_this(l))

发表于 2019-10-13 15:59:25 回复(0)

onceorange

基础的动态规划

#include<iostream>
using namespace std;
#include<vector>
int max(int a,int b)
{
    return a>b?a:b;
}
int max(int a,int b,int c)
{
    if(a>b&&a>c)
    return a;
    else if(b>a&&b>c)
        return b;
    else
        return c;
}
int main()
{
    int n;cin>>n;
    int temp;
    vector<int>vec;
    for(int i=0;i<4*n;i++)
    {
        cin>>temp;
        vec.push_back(temp);
    }
    int dp[101][121]={{0}};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=120;j++)
        {
            if(vec[4*(i-1)]>j)
                dp[i][j]=dp[i-1][j];
            else if(vec[4*(i-1)]<=j&&j<vec[4*(i-1)+2])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vec[4*(i-1)]]+vec[4*(i-1)+1]);
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vec[4*(i-1)]]+vec[4*(i-1)+1],dp[i-1][j-vec[4*(i-1)+2]]+vec[4*(i-1)+3]);            
        }
    cout<<dp[n][120]<<endl;
    return 0;
}

发表于 2019-07-27 21:14:53 回复(0)

lzher0

n = int(input())
weight = []
value = []
for i in range(n):
    w1, v1, w2, v2 = map(int, input().split())
    weight.append([w1, w2])
    value.append([v1, v2])

dp = [0]*121
for i in range(n):
    for j in range(120,0, -1):
        if j >= weight[i][0] or j >= weight[i][1]:
            if j >= weight[i][0] and j >= weight[i][1]:
                dp[j] = max(dp[j-weight[i][0]]+value[i][0], dp[j-weight[i][1]]+value[i][1], dp[j])
            elif j >= weight[i][0]:
                dp[j] = max(dp[j-weight[i][0]]+value[i][0], dp[j])
            else:
                dp[j] = max(dp[j-weight[i][1]]+value[i][1], dp[j])
print(dp[120])

发表于 2019-07-23 08:54:19 回复(0)

多多核心收割机

import java.util.Scanner;

/**
 * 考试策略，典型的多重背包问题
 * @author DELL
 *
 */
public class Main5 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] value = new int[N][2];
        int[][] weight = new int[N][2];
        for(int i = 0; i < N; i++) {
            weight[i][0] = sc.nextInt();
            value[i][0] = sc.nextInt();
            weight[i][1] = sc.nextInt();
            value[i][1] = sc.nextInt();
        }
        int[] dp = new int[121];
        for(int i = 0; i < N; i++) {
            for(int j = 120; j >= weight[i][0] || j >= weight[i][1]; j--) {
                if(j >= weight[i][0] && j >= weight[i][1]) {
                    dp[j] = Math.max(Math.max(dp[j-weight[i][0]] + value[i][0], dp[j-weight[i][1]] + value[i][1]), dp[j]);
                }else if(j >= weight[i][0]) {
                    dp[j] = Math.max(dp[j-weight[i][0]] + value[i][0], dp[j]);
                }else {
                    dp[j] = Math.max(dp[j-weight[i][1]] + value[i][1], dp[j]);
                }
            }
        }
        System.out.println(dp[120]);
    }
}

发表于 2019-07-11 21:25:03 回复(0)

我叫小白，叫我焦尼就好了

import java.util.Scanner;

public class Main {
    // static int[] s;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] pi = new int[n];
        int[] ai = new int[n];
        int[] qi = new int[n];
        int[] bi = new int[n];
        int index = 0;
        while (in.hasNextInt()) {// 注意while处理多个case
            pi[index] = in.nextInt();
            ai[index] = in.nextInt();
            qi[index] = in.nextInt();
            bi[index] = in.nextInt();
            index++;
        }
        in.close();

        int[] dp = new int[121];
        for (int j = 1; j <= n; j++) {
            int[] dp2 = new int[121];
            for (int i = 1; i < 121; i++) {
                if (i < pi[j-1]){
                    dp2[i] = dp[i];
                    continue;
                }
                dp2[i] = Math.max(dp2[i - 1], Math.max(dp[i - pi[j-1]] + ai[j-1], dp[i]));
                if (i >= qi[j-1]) {
                    dp2[i] = Math.max(dp2[i], dp[i-qi[j-1]] + bi[j-1]);
                }
            }
            dp = dp2;
        }

        System.out.println(dp[120]);

        return;
    }

}

发表于 2019-06-24 23:27:04 回复(0)