hdu 2546 飯卡（背包）

設飯卡余額為total
此題經分析 可以得出：要求選出一些飯菜 時消費量盡量接近total-5元 然後再買一個飯菜 以達到透支。。。

可以證明 最後買的那個飯菜是飯菜中價值最大的.
證明

設a1 a2 a3...an-1 an 為各飯菜的價格  設an的價格最大

設
sum=total-5
a1+a2+a3+...an-2+an-1+an=M
a1+a2+a3+...+an-2+an-1=x1          最後加an （按5元為界限）此時超額(an-1)-(sum-x1)=an-sum+a1+a2+...+an-2+an-1元                1
a1+a2+a3+...+an-2+an=x2             最後加an-1（按5元為界限）此時超額(an)-(sum-x2)=(an-1)-sum+a1+a2+...+an-2+an元              2

1式-2式=2*((an)-(an-1))>0
所以1式超額更多
所以最後選價格最大的那個飯菜得證

此題注意一點： 如果余額total本身就少於5元  直接輸出total     此時沒法買東西了  這種特殊情況要判斷

動態規劃
01背包問題 背包總量為余額-5  每個背包價值和重量都為w

#include<stdio.h>

#include<string.h>
#include<stdlib.h>
#define max(a,b) a>b?a:b
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
int main()
{
int n,a[5000],i,bb[5000],m,j;
while(scanf("%d",&n),n!=0)
{
memset(bb,0,sizeof(bb));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
qsort(a,n,sizeof(a[0]),cmp);
if(m<5)
{
printf("%d\n",m);
continue;
}
memset(bb,0,sizeof(bb));
m=m-5;
bb[0]=0;
for(i=0;i<n-1;i++)
{
for(j=m;j>=a[i];j--)
{
bb[j]=max(bb[j],bb[j-a[i]]+a[i]);
}
}
printf("%d\n",m+5-bb[m]-a[n-1]);
}
return 0;

}