codeforces（排序 + 01背包）

本文主要是介绍codeforces（排序 + 01背包），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 问题描述：

牛牛正在打一场CF，比赛时间为T分钟，有N道题，可以在比赛时间内的任意时间提交代码，第i道题的分数为maxPoints[i],题目的分数随着比赛的进行，每分钟减少pointsPerMinute[i]，这是一场比较dark的Cf，分数可能减成负数，已知第i道题需要花费 requiredTime[i] 的时间解决，请问最多可以得到多少分？

输入描述:
第一行输入两个整数N,T (1 ≤ N ≤ 50, 1 ≤ T ≤ 100000)
第二行输入n个整数maxPoints[i]
第三行输入n个整数pointsPerMinute[i]
第四行输入n个整数requiredTime[i]
1 ≤ maxPoints[i],pointsPerMinute[i],requiredTime[i] ≤ 100000

输出描述:
输出一个整数
示例1
输入
1 74
502
2
47
输出
408
示例2
输入
2 40000
100000 100000
1 100000
50000 30000
输出
0
示例3
输入
3 75
250 500 1000
2 4 8
25 25 25
输出
1200
示例4
输入
3 30
100 100 100000
1 1 100
15 15 30
输出
97000
备注:
子任务1: n <= 10
子任务2: n <= 20
子任务3: 无限制

链接：https://ac.nowcoder.com/acm/problem/21314
来源：牛客网

2. 思路分析：

① 分析题目可以知道这道题目的本质是01背包模型，只是在问题的描述上与01背包略有不同但是将其转换为01背包问题那么就很容易理解了。比赛时间为T分钟相当于是背包的最大容量为T，N道题目相当于是相当于是N个物品，每道题目的分数相当于是物品的价值，这道题目多了一个限制为：随着比赛的进行每道题目会减去一定的分数，对于题目的这个限制我们其实可以先解决那些时间比较短的时间下消耗分数比较多的题目，具体来说就是先解决单位时间内消耗分数多的题目，对于这个条件我们可以对控制台输入的maxPoints，pointsPerMinute，requiredTime作为一个整体按照单位时间消耗分数多的由大到小进行排序。接下来就可以使用一维的列表或者数组（python为列表，c/c++/java为数组）解决01背包问题。在背包容量允许的前提下下尝试将当前的物品放入到背包中看价值是否更大，因为随着比赛的进行每道题目会减去一定的分数的限制条件，所以我们在计算当前的dp[i]的时候需要减去当前的时间乘以这道题目每分钟消逝的分数。总体来说就是排序（限制条件）+ 01背包模型。

② 一开始的时候使用的是python语言但是提交上去超时了，后面将相同的思路改为了java代码解决提交上去通过了。python语言可以使用元组将三个maxPoints，pointsPerMinute，requiredTime作为元组的元素添加到列表中这样后面就可以对列表中的元素使用lambda表达式进行排序，lambda表达式中规定排序的规则即可。java语言可以使用对象数组来存储第i道三个属性值然后使用lambda表达式规定排序的规则对对象数组排序即可（对象数组使用lambda表达式自定义排序规则实现整体排序）。需要注意的一个问题是dp数组需要声明为long类型这样才不会发生溢出的情况（一开始的时候声明为int发生了溢出的情况）

3. 代码如下：

java代码：

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
    public static class Node{
        long mPoints, pointsPerMinute, requiredTime;
        public long getmPoints() {
            return mPoints;
        }

        public long getPointsPerMinute() {
            return pointsPerMinute;
        }

        public long getRequiredTime() {
            return requiredTime;
        }

        public Node(long mPoints, long pointsPerMinute, long requiredTime){
            this.mPoints = mPoints;
            this.pointsPerMinute = pointsPerMinute;
            this.requiredTime = requiredTime;
        }

        @Override
        public String toString() {
            return mPoints + " " + pointsPerMinute + " " + requiredTime;
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner((System.in));
        int n = sc.nextInt();
        int t = sc.nextInt();
        int[] maxPoints = new int[n];
        int[] pointsPerMinute = new int[n];
        int[] requiredTime = new int[n];
        for (int i = 0; i < n; ++i){
            maxPoints[i] = sc.nextInt();
        }
        for (int i = 0; i < n; ++i){
            pointsPerMinute[i] = sc.nextInt();
        }
        for (int i = 0; i < n; ++i){
            requiredTime[i] = sc.nextInt();
        }
        Node nodes[] = new Node[n];
        for (int i = 0; i < n; ++i){
            nodes[i] = new Node(maxPoints[i], pointsPerMinute[i], requiredTime[i]);
        }
        // 对象数组排序排序的规则
        Comparator<Node> cmp = (o1, o2) -> {
            if ((float)o1.pointsPerMinute / o1.requiredTime > (float)o2.pointsPerMinute / o2.requiredTime){
                return -1;
            }else if ((float)o1.pointsPerMinute / o1.requiredTime < (float)o2.pointsPerMinute / o2.requiredTime){
                return 1;
            }
            return 0;
        };
        Arrays.sort(nodes, cmp);
        long dp[] = new long[t + 1];
        long res = 0;
        for (int i = 0; i < n; ++i){
            for (int j = t; j >= nodes[i].requiredTime; j--){
                dp[j] = Math.max(dp[j], dp[(int) (j - nodes[i].requiredTime)] + nodes[i].mPoints - j * (nodes[i].pointsPerMinute));
                res = Math.max(res, dp[j]);
            }
        }
        System.out.println(res + " ");
    }
}

python代码：

if __name__ == '__main__':
    n, t = map(int, input().split())
    maxPoints, pointsPerMinute, requiredTime = list(map(int, input().split())), list(map(int, input().split())), list(map(int, input().split()))
    p = list(zip(maxPoints, pointsPerMinute, requiredTime))
    # 自定义排序规则: 按照单位时间内的消耗分数由大到小进行排序
    p.sort(key=lambda x: (x[1] / x[2]), reverse=True)
    # print(p)
    # 接下来的就是01背包问题
    dp = [0] * (t + 1)
    res = 0
    for i in range(n):
        j = t
        while j >= p[i][2]:
            dp[j] = max(dp[j], dp[j - p[i][2]] + p[i][0] - j * p[i][1])
            res = max(res, dp[j])
            j -= 1
    print(res)

这篇关于codeforces（排序 + 01背包）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！