华为机试3——工程最大利润

题目描述

现有若干工程项目，你可以选择最多P项，你有初始资本W。每一个工程 i 有净利润（除去成本）profit_i，但是你选择的工程需要至少有 capital_i 的原始资本。请你选择工程 使得总利润最高，需要注意的是，一个工程只能选择一次。

输入

第一行输入一个值P 第二行输入一个值W 第三行输入一行若干个数，用逗号隔开，第 i 个数表示对应第 i 个工程能够获取的净利润； 第四行输入一行若干个数，用逗号隔开，第 i 个数表示对应第 i 个工程所需要的资本；

输出

输出一个值 为能获得的最大利润；

测试样例

输入： 2 0 1,2,3 0,1,1

1. 你可以选择最多2个项目；
2. 一开始你有起始资本0；
3. 因此你只能选择第一个工程项目即需要启动资本0，利润1（其余两个启动资本都大于0，无法启动）；
4. 第一个工程完成，你有利润1，即此时资本也变为1，即可启动剩下2个工程，当然选择第3个工程，利润3；
5. 因此，最终你获得的利润为1+3=4，输出4；

注意：启动资本不是成本，不会被消耗；

机试时思路

类似贪心算法的01背包问题，先考虑该工程是否能做，（包含判断该工程的启动资本是否小于等于当前资本，判断该工程是否已经做过）在能做的工程里面，选择收益最高的一项。这就是一次工程的选择的过程，记录每次获得的利润，最后输出。

import java.util.Scanner;
import java.lang.Math;

public class Main3{
          
   
    
    public static void main(String[] args){
          
   
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int W = sc.nextInt();
        
        String profitString = sc.next();
        String[] profitArray = profitString.split(",");
        int[] profit = new int[profitArray.length];
        for(int i=0;i<profit.length;i++){
          
   
            profit[i] = Integer.valueOf(profitArray[i]);
        }
        
        String capitalString = sc.next();
        String[] capitalArray = capitalString.split(",");
        int[] capital = new int[capitalArray.length];
        for(int i=0;i<capital.length;i++){
          
   
            capital[i] = Integer.valueOf(capitalArray[i]);
        }
        
        boolean[] visited = new boolean[capital.length];
        

        for(int i=0;i<K;i++){
          
   
            int maxProfit=0;
            int profit_index=-1;
            for(int j=0;j<capital.length;j++){
          
   
                if(capital[j]>W)
                    continue;
                
                if(profit[j]>maxProfit && !visited[j]){
          
   
                    maxProfit = profit[j];
                    profit_index=j;
                }
                
            }
            W+=maxProfit;
            visited[profit_index] =true;
        }
        
        System.out.println(W);
    }
}

算法的时间复杂度O(W*n)，n为工程总数，空间复杂度为O(n)，需要用到一个visited数组来记录和判断一项工程是否做过。