A - 小彭玉的扫荡食堂计划
Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Problem Description
哗啦啦村的食堂很奇怪，就是如果这个饭卡所剩金额低于5元的话，这个饭卡就不能刷了。
也就是说，只要这个饭卡金额大于等于5元，就可以随便刷～
有一天，小彭玉看了看哗啦啦食堂的饭，“哇，好好吃！我要全部都买下来！”
但是小彭玉并没有那么多钱，于是他准备充分利用自己的钱，去买这些食物！
请问最后小彭玉的饭卡余额最少能到多少？
Input
多组测试数据（最多100组）
第一行 n，表示有n个菜
第二行 接下来n个数字，a[i]表示第i道菜多少钱
第三行 一个数m，表示小彭玉的饭卡，一开始有m元
1<=n<=1000,1<=a[i]<=10000,1<=m<=10000
Output
输出一个整数，表示最后饭卡显示的金额数
Sample Input
1
10000
6
10
1 2 3 2 1 1 2 3 2 1
50
Sample Output
-9994
32
解法：01背包的使用，因为5块钱可以买任何东西，所以，我们把价格最贵的菜独自拿出来，我们只需要用(N-1)份菜去查找价钱容量为(M-5），所能够买到的最大值。最后在减去价格最大的那份菜的价格即可。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10100
int DP[MAX];
int val[MAX];
int main()
{
int N,M,i,j,Max;
while(scanf("%d",&N)!=EOF)
{
for(i=,Max=;i<N;i++)
{
scanf("%d",&val[i]);
if(val[i]>Max)Max=val[i];/*取最大值*/
}
scanf("%d",&M);
for(i=;i<=M;i++)DP[i]=;
if(M<||N==){printf("%d\n",M);continue;}
else
{
int sign=;
for(i=;i<N;i++)
{
if(sign&&val[i]==Max)/*去除一次最大值*/
{sign=;continue;}
for(j=M-;j>=val[i];j--)
{
if(DP[j]<DP[j-val[i]]+val[i])
{
DP[j]=DP[j-val[i]]+val[i];
}
}
}
printf("%d\n",M-DP[M-]-Max);
}
}
return ;
}