HDOJ 2546 饭卡 (01背包) - c++编程基础

题意：卡内有m元钱，有n种菜可以买（每种菜只可以买一次），只要卡内金额大于等于5元就可以买任何菜（刷到负也可以）。求最少可使卡上的余额为多少。
思路：最贵的一个菜一定是最后买，然后用01背包求（m-5）元钱可买的菜的最大金额，然后（m-最大金额-最贵的菜的价钱）即为所求。
[cpp]
#include
#include

#define maxn 1111

int val[maxn],f[maxn];

main()
{
int n,m,i,j,max,pos;
while(scanf("%d",&n)&&n)
{
for(i=1;i<=n;i++)
scanf("%d",&val[i]);
scanf("%d",&m);
if(m<5)
{
printf("%d\n",m);
continue;

}
for(max=-1,pos=0,i=1;i<=n;i++)
if(max {
max=val[i];
pos=i;
}
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
{
if(pos==i)
continue; www.2cto.com
for(j=m-5;j>=val[i];j--)
if(f[j] f[j]=f[j-val[i]]+val[i];
}
printf("%d\n",m-f[m-5]-max);
}
return 0;
}
作者：sdc1992