#1353 : 满减优惠

时间限制:

10000ms

单点时限:

1000ms

内存限制:

256MB

描述

最近天气炎热，小Ho天天宅在家里叫外卖。他常吃的一家餐馆一共有N道菜品，价格分别是A₁, A₂, ... A_N元。并且如果消费总计满X元，还能享受优惠。小Ho是一个不薅羊毛不舒服斯基的人，他希望选择若干道不同的菜品，使得总价在不低于X元的同时尽量低。

你能算出这一餐小Ho最少消费多少元吗？

输入

第一行包含两个整数N和X，(1 <= N <= 20, 1 <= X <= 100)

第二行包含N个整数A₁, A_2, ...， A_N。(1 <= A_i <= 100)

输出

输出最少的消费。如果小Ho把N道菜都买了还不能达到X元的优惠标准，输出-1。

样例输入

10 509 9 9 9 9 9 9 9 9 8

样例输出

53 分析：01背包。把所有菜价格的总和sum跟X的差值d 作为背包容量，然后把结果无限接近d。

#include
           
            #include
            
             using namespace std;int dp[3000],a[300]; int main(){    int N,X,sum=0;    scanf("%d%d",&N,&X);    for(int i=1;i<=N;i++)    {scanf("%d",&a[i]);sum+=a[i];}    int d=sum-X;    if(d<0) printf("-1\n");    else if(d==0) printf("%d\n",sum);    else//差值d为背包     {        for(int i=1;i<=N;i++)        {            for(int j=d;j>=a[i];j--)            if(dp[j-a[i]]+a[i]<=d)            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);        }        int ans=0;        for(int i=0;i<=d;i++)            ans=max(dp[i],ans);        printf("%d\n",sum-ans);    }    return 0;}