小红书329编程题第二题题解

背包问题。类似的题目有leetcode152, 还有买卖股票的最佳时机III leetcode 123

import java.util.*;
public class Xiaohongshu329_2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        int[] array = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            array[i] = in.nextInt();
        }
        
        int[][] dp0 = new int[n + 1][x + 1]; //dp0表示没有使用多次推荐的
        int[][] dp1 = new int[n + 1][x + 1]; //dp1表示使用了多次推荐的
        
        for (int i = 1; i <= x; i++) { //初始化
            dp0[0][i] = Integer.MAX_VALUE;
            dp1[0][i] = Integer.MAX_VALUE;
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int value = array[i];
            int half = array[i] / 2;
            for (int j = 1; j <= x; j++) {
                if (j >= half) { //背包问题
                    dp0[i][j] = Math.min(dp0[i - 1][j], dp0[i - 1][j - half] + 1);
                    dp1[i][j] = Math.min(dp1[i - 1][j], dp1[i - 1][j - half] + 1);
                    if (j >= value) {
                        dp1[i][j] = Math.min(dp1[i][j], dp0[i - 1][j - value] + 1); //在该位置处使用多次推荐
                    }
                } else {
                    dp0[i][j] = dp0[i - 1][j];
                    dp1[i][j] = dp1[i - 1][j];
                }
            }
        }
        ans = Math.min(dp0[n][x], dp1[n][x]);
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}