途虎养车笔试(编程题)

1.

模拟题 ;

2.

给你n个任务，开始时间为st[i],结束时间为ed[i],该任务的收益为ps[i],一个任务结束之后，你可以马上开始下一个任务，但你同一时间只能运行一个任务，求出你可能得到的最大收益 ;

lc 1235;

class Solution {
    public int jobScheduling(int[] st, int[] ed, int[] pt) {
        // 按照结束时间排序，然后dp ;
        // dp[i] : 前i个工作结束的最大酬劳
        //  不选i : dp[i] = dp[i-1] ;
        //  选i : dp[i] = dp[j]+profit[i] (ed[j]<=st[i])
        // so : dp[i] = max(dp[i-1],dp[j]+pt[i]) ;
        int n = st.length ;
        int[][] jobs = new int[n][] ;
        for(int i=0;i<n;i++){
            jobs[i] = new int[]{ed[i],st[i],pt[i]} ;
        }
        Arrays.sort(jobs,(a,b)->a[0]-b[0]) ;
        int[] dp = new int[n+1] ;
        dp[0] = 0 ;
        for(int i=0;i<n;i++){
            int j = ef(jobs,i,jobs[i][1]) ;
            dp[i+1] = Math.max(dp[i],dp[j+1]+jobs[i][2]) ;
        }
        return dp[n] ;
    }
    // 查找ed<=m的最大下标
    private int ef(int[][] jobs,int r,int m){
        int l = -1 ;
        // 双开二分
        while(l+1<r){
            int mid = (l+r)/2 ;
            if(jobs[mid][0]<=m) l = mid ;
            else r = mid ;
        }
        return l ;
    }
}

3.

给你n个货物，有重量w和体积v，要放入一辆小车中，小车有最大承重Max_w和最大体积Max_v限制,求最多放入几个物品 ;

二维费用背包问题 ，例题链接 : https://www.acwing.com/problem/content/description/8/

import java.util.* ;

public class Main {
    static int N = 110 ;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in) ;
        // StringBuilder sb = new StringBuilder() ;
        int n = sc.nextInt() ,V = sc.nextInt() ,M =sc.nextInt() ;
        int[][] f = new int[N][N] ;
        // f[i][j][k] : 选前i个物品，体积不超过j，重量不超过k的最大价值
        // f[i][j][k] = max(f[i-1][j][k],f[i-1][j-v[i]][k-m[i]]+w[i]) ;
        // 只和上一轮有关，那么可以优化一轮
        for(int i=1;i<=n;i++){
            int v = sc.nextInt(),m = sc.nextInt() ,w = sc.nextInt();
            for(int j=V;j>=v;j--){
                for(int k=M;k>=m;k--){
                    f[j][k] = Math.max(f[j][k],f[j-v][k-m]+w) ;
                }
            }
        } 
        int ans = f[V][M] ;
        System.out.println(ans);
        sc.close(); 
    }
}