学步园

设计简单策略，将问题变形：最后购买的物品必然是最贵的，而其他物品使剩余金额最靠近5￥，进而可以说花掉的钱更多，这就是一个略特殊的01背包。最后的答案是剩余金钱减去最贵者的价格。

先附二维写法以明示思路：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int price[1005];
int f[1005][1005];
int main()
{
   int n,money;
   while(scanf("%d",&n)==1)
   {
      if(n==0)break;
      int sum=0;
      for(int i=1;i<=n;i++)
      {
         scanf("%d",&price[i]);
         sum+=price[i];
      }
      scanf("%d",&money);
      if(money<5)
      {
         printf("%d\n",money);
         continue;
      }
      if(money-sum>=5)
      {
         printf("%d\n",money-sum);
         continue;
      }
      memset(f,0,sizeof(f));
      for(int i=0;i<=n;i++)
      {
         f[0][i]=i;
      }
      for(int i=1;i<=n;i++)
      {
         for(int m=0;m<=money;m++)
         {
            if(m<5)f[i][m]=m;
            else if(m-price[i]<5)
               f[i][m]=min(m-price[i],f[i-1][m]);
            else
               f[i][m]=min(f[i-1][m],f[i-1][m-price[i]]);
            f[i][m]=min(f[i][m],f[i][m-1]);
         }
      }
      /*for(int i=1;i<=money;i++)
        {
        printf("%d ",f[n][i]);
        if(i%10==0)puts("");
        }*/
      printf("%d\n",f[n][money]);
   }
   return 0;
}