牛客网真题-79-外卖满减-美团MT46

01背包，动态规划，dp[x+1],定义未达到i元的最低消费，剩下j元，对于当前物品int[i]，价值和花费为int[i]，是否购买当前物品分两种情况：
当前价值j不够或者刚好能够购买物品i，买了物品i不能买其他物品了，dp[j]是前i-1件的最小价值，与当前价值作比较；
当前价值j超过了物品i的价值，买了物品i，还能买其他物品。

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int[] ints = new int[n];
        for(int i = 0; i < n; i++){
            ints[i] = scanner.nextInt();
        }
        int[] dp = new int[x + 1]; //dp[i] 达到i元的最低消费
        dp[0] = 0;
        Arrays.fill(dp, 10001);
        for(int i = 0; i < n; i++){
            for(int j = dp.length - 1; j >= 0; j--){
                if(j > ints[i]){
                    dp[j] = Math.min(dp[j], dp[j - ints[i]] + ints[i]);
                }else{
                    dp[j] = Math.min(dp[j], ints[i]);
                }
            }
        }
        System.out.println(dp[x]);
    }
}