求看完所有电影的最少天数：每日观影时长上限3.00

给定一个存储电影时长的double数组，每日观影总时长上限为3.00，需计算看完所有电影所需的最少天数。
约束条件：

• 每部电影时长满足 1.01 ≤ duration[i] ≤ 3.00
• 每部电影仅能观看一次，可自由选择每日观看的影片组合

样例测试用例 #

• 输入：duration[] = {1.01, 2.4, 1.01, 1.01, 1.4} → 输出：3
• 输入：duration[] = {1.01, 2.4, 1.4, 1.6, 2.6, 1.7} → 输出：4
• 输入：duration[] = {1.01, 2.4, 1.5, 1.6, 2.6, 1.7} → 输出：5

我的实现情况 #

这是校园招聘笔试中的题目，当时没能按时完成。后续我用递归实现了代码，能通过部分自定义测试用例，但不确定是否覆盖所有场景，同时希望优化时间复杂度，寻求帮助。

核心思路 #

由于每部电影时长≥1.01，每日最多只能观看2部电影（3部总时长必然超过3.00）。

代码实现 #

import java.util.ArrayList;

public class MoviesBetterSolution {

    public static void main(String[] args) {
        double arr[] = {2.0, 1.01, 1.4, 2.4, 1.71};  // 测试用例
        // days初始为1（从第1天开始），wtn（当日已观影时长）初始为0.00
        System.out.println(f(0, 0.00, 1, 3.00, new ArrayList<Integer>(), arr, 0));
    }   

    static int minDays = Integer.MAX_VALUE;

    // wtn: 当日已观影时长
    // taken: 当日已观看的电影数量
    // picked: 已观看的电影索引集合
    private static int f(int i, double wtn, int days, double limit, ArrayList<Integer> picked, double[] arr, int taken) {
        // 所有电影看完时，更新最小天数
        if (picked.size() == arr.length) {
            if (days < minDays) minDays = days;
            return minDays;  
        }

        // 遍历完数组时的处理
        if (i == arr.length) {  
            if (taken != 0) {     // 当日至少看了1部，重新遍历未观看影片，开启新遍历
                i = 0;         
                taken = 0;            
            } else {       // 当日未看电影，直接返回避免栈溢出
                return minDays;            
            }       
        }

        // 仅处理未观看且加入后不超当日时长上限的电影
        if ((wtn + arr[i] <= limit) && !picked.contains(i)) {  
            ArrayList<Integer> temp = (ArrayList<Integer>) picked.clone();
            temp.add(i);
            if (taken < 2) { // 当日最多看2部，继续在当日处理下一部
                f(i+1, wtn + arr[i], days, limit, temp, arr, taken+1);            
            }
            // 观看当前电影后直接结束当日，开启新一天
            f(0, 0, days + 1, limit, temp, arr, taken+1);        
        }

        // 不观看当前电影，继续处理下一部
        f(i+1, wtn, days, limit, picked, arr, taken);

        return minDays;   
    } 
}

内容的提问来源于stack exchange，提问作者Priyansh Gaurav