题解 | 外卖满减

def solve():
    # 读取输入
    n, x = map(int, input().split())
    prices = list(map(int, input().split()))
    
    # 初始化dp数组
    dp = [[False] * 10001 for _ in range(n + 1)]
    dp[0][0] = True
    
    # 动态规划
    for i in range(n):
        for j in range(10001):
            # 不选第i个菜
            dp[i + 1][j] = dp[i][j]
            # 选第i个菜
            if j >= prices[i]:
                dp[i + 1][j] |= dp[i][j - prices[i]]
    
    # 从满足条件的最小价格开始找
    for total in range(x, 10001):
        if dp[n][total]:
            print(total)
            break

if __name__ == "__main__":
    solve()

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int x = sc.nextInt();
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextInt();
        }
        
        // 初始化dp数组
        boolean[][] dp = new boolean[n + 1][10001];
        dp[0][0] = true;
        
        // 动态规划
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 10000; j++) {
                // 不选第i个菜
                dp[i + 1][j] = dp[i][j];
                // 选第i个菜
                if (j >= prices[i]) {
                    dp[i + 1][j] |= dp[i][j - prices[i]];
                }
            }
        }
        
        // 从满足条件的最小价格开始找
        for (int total = x; total <= 10000; total++) {
            if (dp[n][total]) {
                System.out.println(total);
                break;
            }
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取输入
    int n, x;
    cin >> n >> x;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }
    
    // 初始化dp数组
    vector<vector<int>> dp(n + 1, vector<int>(10001, 0));
    dp[0][0] = 1;
    
    // 动态规划
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= 10000; j++) {
            // 不选第i个菜
            dp[i + 1][j] = dp[i][j];
            // 选第i个菜
            if (j >= prices[i]) {
                dp[i + 1][j] |= dp[i][j - prices[i]];
            }
        }
    }
    
    // 从满足条件的最小价格开始找
    for (int total = x; total <= 10000; total++) {
        if (dp[n][total]) {
            cout << total << endl;
            break;
        }
    }
    
    return 0;
}