飯卡

Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4160????Accepted Submission(s): 1410

Problem Description 電子科大本部食堂的飯卡有一種很詭異的設(shè)計，即在購買之前判斷余額。如果購買一個商品之前，卡上的剩余金額大于或等于5元，就一定可以購買成功（即使購買后卡上余額為負(fù)），否則無法購買（即使金額足夠）。所以大家都希望盡量使卡上的余額最少。
某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的余額，問最少可使卡上的余額為多少。

?

Input 多組數(shù)據(jù)。對于每組數(shù)據(jù)：
第一行為正整數(shù)n，表示菜的數(shù)量。n<=1000。
第二行包括n個正整數(shù)，表示每種菜的價格。價格不超過50。
第三行包括一個正整數(shù)m，表示卡上的余額。m<=1000。

n=0表示數(shù)據(jù)結(jié)束。

?

Output 對于每組輸入,輸出一行,包含一個整數(shù)，表示卡上可能的最小余額。

?

Sample Input 1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

?

Sample Output -45 32

?

Source UESTC 6th Programming Contest Online

?

Recommend lcy code: 1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 6 int dp[1010]; 7 int data[1010]; 8 int n,m; 9 10 int cmp(int a,int b) 11 { 12 return a>b; 13 } 14 15 int main() 16 { 17 int i,j; 18 while(~scanf("%d",&n),n) 19 { 20 for(i=0;i<n;i++) 21 scanf("%d",&data[i]); 22 scanf("%d",&m); 23 if(m<5) 24 { 25 printf("%d\n",m); 26 continue; 27 } 28 sort(data,data+n,cmp); 29 m-=5; 30 for(i=0;i<=m;i++) 31 dp[i]=m; 32 for(i=1;i<n;i++) 33 { 34 for(j=m;j>=data[i];j--) 35 { 36 dp[j]=dp[j]>dp[j-data[i]]-data[i]?dp[j-data[i]]-data[i]:dp[j]; 37 } 38 } 39 int gmin=9999999; 40 for(i=0;i<=m;i++) 41 if(dp[i]<gmin) 42 gmin=dp[i]; 43 printf("%d\n",gmin+5-data[0]); 44 } 45 return 0; 46 }

?

總結(jié)

以上是生活随笔為你收集整理的HDOJ---2546 饭卡[DP01背包问题]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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