#1353 : 滿減優(yōu)惠

時間限制:10000ms 單點時限:1000ms 內(nèi)存限制:256MB

描述

最近天氣炎熱，小Ho天天宅在家里叫外賣。他常吃的一家餐館一共有N道菜品，價格分別是A₁, A₂, ... A_N元。并且如果消費總計滿X元，還能享受優(yōu)惠。小Ho是一個不薅羊毛不舒服斯基的人，他希望選擇若干道不同的菜品，使得總價在不低于X元的同時盡量低。

你能算出這一餐小Ho最少消費多少元嗎？

輸入

第一行包含兩個整數(shù)N和X，(1 <= N <= 20, 1 <= X <= 100)

第二行包含N個整數(shù)A₁, A_2, ...， A_N。(1 <= A_i <= 100)

輸出

輸出最少的消費。如果小Ho把N道菜都買了還不能達到X元的優(yōu)惠標準，輸出-1。

樣例輸入

10 50 9 9 9 9 9 9 9 9 9 8

樣例輸出

53


分析：01背包。把所有菜價格的總和sum跟X的差值d
作為背包容量，然后把結(jié)果無限接近d。

#include<cstdio> #include<algorithm> 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; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/ACRykl/p/8215642.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder1353 满减优惠的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。