飯卡(card)

Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 253 Tried: 2169

Submit

Status

Best Solution

Back

Description

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

// f[i][j] ：前i個(gè)物品能否把空間j填滿
// f[i][j]=f[i][j]==1?f[i][j]:f[i-1][j-r[i]]
// f[i][0]=1;解為 小于等于m-5的空間中 可以被填滿的最大值 
// 根據(jù)0,1 背包 這里可以利用滾動(dòng)數(shù)組 所以將f降到1維
// 把最大值單獨(dú)提取出來、、剩余用來做0,1背包 為什么這樣做是對(duì)的
// 證明 ： 假設(shè) 將最大值Max用來求0,1 背包, 則設(shè)比Max小的數(shù)在集合 s{..}中
// 最后打的菜價(jià)為 P 則 sigma S{..}+Max+P 就是所花的錢。 m-sigma S{..}-Max-P就是飯卡最后剩下的錢
// 若用P來代替 Max, Max代替P 則結(jié)果是一樣的， 其中還有可能 P+T{..}=Max 這樣的話 剩余的錢就是
//m-sigma S{..}-Max-P-sigma T{..} 明顯還更小、所以將最大的值用來當(dāng)做最后一個(gè)菜來打肯定正確
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
using namespace std;
int r[1010];
int n,m;
int f[1010];
int main()
{while(scanf("%d",&n),n){int i,j;for(i=0;i<n;i++)scanf("%d",&r[i]);sort(r,r+n);scanf("%d",&m);if(m<5) { printf("%d\n",m);continue;}memset(f,0,sizeof(f));for(i=0;i<n-1;i++)for(j=m-5;j>=r[i];j--)if(j==r[i]) f[j]=1;elsef[j]=f[j]|f[j-r[i]];for(i=m-5;i>0;i--)if(f[i])break;printf("%d\n",m-r[n-1]-i);}return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/372465774y/archive/2013/04/22/3036124.html

總結(jié)

以上是生活随笔為你收集整理的uestc 1012 饭卡的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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