java - Hackerrank Mark 和 Toys 质疑我的解决方案不适用于大型输入测试用例

Question

以下是hackerrank的问题陈述

生了第一个孩子后，马克和简非常高兴。他们的儿子喜欢玩具，所以马克想买一些。他面前摆着许多不同的玩具，上面标有价格。马克只有一定的钱可以花，他想用这笔钱尽可能多地购买玩具。

给定价格清单和消费金额，马克最多可以购买多少玩具？例如，如果价格 = [1,2,3,4] 并且马克有 k=7 的花费，他可以以 6 的价格购买物品 [1,2,3]，或以 7 个单位的货币购买 [3,4]。他会选择第一组 3 个项目。

下面是我为这个问题编写的涉及回溯技术的代码

import java.util.ArrayList;
import java.util.Collections;

public class MarkAndToys {

    static ArrayList<Integer> possibleSolutions = new ArrayList<>();

    static boolean findSolution(int[] prices,int amount,int left,int length,int items){

        // Base case: if whole array was iterated and amount is >=0 then we got a solution
        if(left >= length){
         if(amount>=0){
             possibleSolutions.add(items);
             return true;
         }
         return false;
        }

        // Key idea: prices[left] is chosen or it is not.
        // Deal with prices[left], letting recursion
        // deal with all the rest of the array.

        // Recursive call trying the case that prices[left] is chosen --
        // subtract it from amount in the call.
        if (findSolution(prices,amount-prices[left],left+1,length,items+1)) return true;

        // Recursive call trying the case that prices[left] is not chosen.
        if (findSolution(prices,amount,left+1,length,items)) return true;

        // If neither of the above worked, it's not possible.
        return false;
    }

    // Complete the maximumToys function below.
    static int maximumToys(int[] prices, int k) {
        if(findSolution(prices,k,0,prices.length,0)){
            //if solutions are found then return maximum of them
            return Collections.max(possibleSolutions);
        }
        return 0;
    }



    public static void main(String[] args) {
        System.out.println(maximumToys(new int[]{1,12,5,111,200,1000,10}, 50));
    }

}

标签： java

Answer 1

这似乎工作正常：

// Complete the maximumToys function below.
static int maximumToys(int[] prices, int k) {
    Arrays.sort(prices);
    int sum = 0;
    int index = 0;
    for(int i = 0; i < prices.length; i++) {
        sum+=prices[i];
        index = i;
        if(sum > k) {
            break;
        }
    }

    return index;

}