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

Input

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

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

Output

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

Sample Input

1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0

Sample Output

-45 32

解題報(bào)告：

? ?這道題也可以說是剛剛接觸背包問題的小菜鳥必做的一道題了。解出這道題的關(guān)鍵在于怎么處理這個(gè)5元。我們的處理方式是，對(duì)余額-5 并將最貴的菜踢出去，然后對(duì)這個(gè)新余額和剩余的n-1個(gè)物品進(jìn)行0-1背包，解出能購買的最大價(jià)值。

? ?這種做法的正確性在此稍作說明：

? ? ? ? ? ? 首先因?yàn)槲覀冃枰囝~最小，所以直觀上我們肯定想把最貴的放在最后一個(gè)買，這樣直接拉開差距。但是有的同學(xué)會(huì)反過來想，那我萬一是把最貴的物品放到背包里面去跑，然后這樣可能更能填滿呢，（即最能使余額接近5元）然后此時(shí)我再拿一個(gè)第二貴的去使余額變?yōu)樨?fù)數(shù)，這樣有可能更好啊。。嗯，這樣想是沒有問題的，但是你要這么想啊，既然你這樣，那還是說明用到了最貴的物品，只是放到背包中了，其實(shí)相當(dāng)于背包中放物品的次序換了一下，該放的物品還是那些物品，所以并不會(huì)影響最終的答案啊，而你如果在n-1個(gè)物品背包的時(shí)候沒有用到最貴的物品，那何必要讓第二貴的去當(dāng)最后一個(gè)使余額變負(fù)數(shù)的物品呢？用最貴的豈不是更好？

? ? ? ? ? ?綜上，我們得出結(jié)論，把最貴的物品貪心出來，然后對(duì)剩下的物品進(jìn)行0-1背包的做法是正確的。

為了加深對(duì)本題的理解，這里附上三種方法，三種代碼：

AC代碼1：（普通的0-1背包）

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m; int v[1000 +5]; int dp[1000 + 5]; int main() {while(~scanf("%d",&n) ) {if(n == 0 ) break;memset(dp,0,sizeof(dp));for(int i = 1; i<=n; i++) {cin>>v[i];}cin>>m;sort(v+1,v+n+1);m-=5;if(m < 0) {printf("%d\n",m+5);continue;}for(int i = 1; i<n; i++) {for(int j = m; j>=v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i] ] + v[i]);}}// printf("**%d***%d\n",m,dp[n-1],dp[n]);printf("%d\n",m+5 - dp[m] - v[n]);}return 0 ; }

AC代碼2：（當(dāng)成恰好花費(fèi)做的）

#include<bits/stdc++.h>using namespace std; int dp[1000 + 5]; int v[1000 + 5]; int n,m; int main() {while(~scanf("%d",&n) ) {if(n == 0 ) break;for(int i = 1; i<=n; i++) {scanf("%d",&v[i]);}scanf("%d",&m);m-=5;sort(v+1,v+n+1);int tmp = v[n];if(m < 0) {printf("%d\n",m+5);continue;}for(int i = 1; i<=1001; i++) dp[i] = - 0x3f3f3f3f;//這里剛開始寫成i<=2000，把v都覆蓋成了-INF，所以直接錯(cuò)了，要注意啊！從匯編的角度也可以理解這件事情。。。自己想想吧。，dp[0]=0;for(int i = 1; i<n; i++) {for(int j = m; j>=v[i]; j--) {dp[j] = max(dp[j],dp[j-v[i]] + v[i]);}}int res = 0;for(int i = m; i>=0; i--) {if(dp[i]>=0) {res = dp[i];break;}}printf("%d\n", m + 5 -res - tmp );}return 0; }

?AC代碼3：（因?yàn)閱蝹€(gè)物品的最大花費(fèi)是50元，所以我在余額上統(tǒng)一+50元，最后在減去這50元，這做法就不需要排序貪心了）

#include<bits/stdc++.h> #define nn 1100 #define inff 0x3fffffff using namespace std;int n,m; int a[nn]; bool dp[nn]; int main() {int i,j;while(scanf("%d",&n),n) {for(i=1; i<=n; i++) {scanf("%d",&a[i]);}scanf("%d",&m);sort(a+1,a+n+1);memset(dp,false,sizeof(dp));dp[m+50]=true;for(i=1; i<=n; i++) {for(j=0; j<=m+50; j++) {if(j+a[i]-50>=5&&j+a[i]<=m+50)dp[j]=dp[j+a[i]]?true:dp[j];}}for(i=0; i<=m+50; i++)if(dp[i])break;printf("%d\n",i-50);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 2546】饭卡 （dp，0-1背包，贪心思想）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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