外卖满减

[编程题]外卖满减

热度指数：5694 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

你打开了美了么外卖，选择了一家店，你手里有一张满 X 元减 10 元的券，店里总共有 n 种菜，第 i 种菜一份需要 A_i 元，因为你不想吃太多份同一种菜，所以每种菜你最多只能点一份，现在问你最少需要选择多少元的商品才能使用这张券。

数据范围： $1 \le n ，A_i \le 100 \$ , $1 \le X \le 10000 \$

输入描述:

第一行两个正整数n和X，分别表示菜品数量和券的最低使用价格。 接下来一行n个整数，第i个整数表示第i种菜品的价格。

输出描述:

一个数，表示最少需要选择多少元的菜才能使用这张满X元减10元的券，保证有解。

示例1

输入

5 20
18 19 17 6 7

输出

算法知识视频讲解

laglangyue

发表于 2020-06-20 21:22:11

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