杭電飯卡問題

Problem Description 電子科大學部食堂的飯卡有一種很詭異的設計，即在購買之前判斷餘額。如果購買一個商品之前，卡上的剩餘金額大于或等于5元，就一定可以購買成功（即使購買後卡上餘額為負），否則無法購買（即使金額足夠）。是以大家都希望盡量使卡上的餘額最少。

某天，食堂中有n種菜出售，每種菜可購買一次。已知每種菜的價格以及卡上的餘額，問最少可使卡上的餘額為多少。

Input 多組資料。對于每組資料：

第一行為正整數n，表示菜的數量。n<=1000。

第二行包括n個正整數，表示每種菜的價格。價格不超過50。

第三行包括一個正整數m，表示卡上的餘額。m<=1000。

n=0表示資料結束。

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

Sample Input

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

Sample Output

-45
32
        

 此題屬于背包問題，隻不過需要 拐一個小彎，即此時相當于背包容量的飯卡餘額需要留出5元來，并且最貴的菜品需要挑出來，等到最後一次消費最貴的才可能讓餘額最小。挑出之後，此題就相當于典型的背包問題，即在餘額未r-5的時候可以最選多少菜品使得卡内餘額最少（即菜品價值最大）。 來看下具體程式：#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int max(int a,int b)

{

return a>b?a:b;

}

int main()

{

    int n,i,j,r;

    while(scanf("%d",&n)!=EOF&&n!=0)

    {

int p[2002]={0},dp[2002];

memset(dp,0,sizeof(dp));

        for(i=0;i<n;i++)

        scanf("%d",&p[i]);

sort(p,p+n);

scanf("%d",&r);

if(r<5)

{

printf("%d\n",r);

continue;

}

r=r-5;

        for(i=0;i<n-1;i++)

   for(j=r;j>=p[i];j--)

   {

dp[j]=max(dp[j],dp[j-p[i]]+p[i]);

   }

   printf("%d\n",r+5-dp[r]-p[n-1]);

    }

    return 0;

}