学步园

具体内容见背包九讲。

相关题目：HDU2159  hdu1114/poj1384（简单变形）  hdu1248（水） hdu2189      POJ2063

hdu1248直接运用01背包模板修改得：

//注意：若n<150,则全部当小费 
#include<iostream>
#include<string.h>
using namespace std;
int f[10010],n;
void ZeroTwoPack(int x)
{
     for(int i=x;i<=n;i++)
     {
         if(f[i]<f[i-x]+x)
         f[i]=f[i-x]+x;
     }
}
int main()
{
    int t;
    int a[3]={150,200,350};
    scanf("%d",&t);
    while(t--)
    {
         scanf("%d",&n);
         if(n<150)
         {
                  printf("%d\n",n);
                  continue;
         } 
         memset(f,0,sizeof(f));
         for(int i=0;i<3;i++)
         {
              ZeroTwoPack(a[i]);
         }
         for(int i=n;i>=0;i--)
         {
              if(f[i]>0)
              {
                   printf("%d\n",n-f[i]);
                   break;
              }
         }
    }
    return 0;
} 

hdu1114同样根据01背包：

#include<iostream>
#include<string.h>
#define INF 0x3fffffff
using namespace std;
int f[10010],sum;
void ZeroTwoPack(int w,int v)
{
     for(int i=v;i<=sum;i++)
     {
        if(f[i]>f[i-v]+w) f[i]=f[i-v]+w;
     }
}
int main()
{
    int t,n,e,fi;
    int v[501],w[501];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&e,&fi);
        sum=fi-e;
        scanf("%d",&n);
        for(int i=1;i<=sum;i++) f[i]=INF; 
        f[0]=0;   //这个对f的初始化很重要，因为是求最少的钱，所以f[1~sum]=INF,但是为了使
                  //函数第一次运行时，能够满足条件，f[0]=0 
        for(int i=0;i<n;i++)
        scanf("%d%d",&w[i],&v[i]);
        for(int i=0;i<n;i++) ZeroTwoPack(w[i],v[i]);
        if(f[sum]!=INF) 
        printf("The minimum amount of money in the piggy-bank is %d.\n",f[sum]);
        else printf("This is impossible.\n");
    }
    return 0;
} 

poj2063 根据输入年数，循环求完全背包，另外需注意每求一次完全背包，钱的总数都要改变，而且因为钱的总数可能很大，所以，将它进行/1000处理（都是1000倍数）。

#include<iostream>
#include<string.h>
#include<stdio.h>
#define size 50000
using namespace std;
int f[size];
void zeroTwoPack(int sum,int v,int w)
{
     for(int i=v;i<=sum;i++)
     if(f[i]<f[i-v]+w)  f[i]=f[i-v]+w; 
     return;
}
int main()
{
    int t;
    int sum,year,num;
    int v[11],w[11];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&sum,&year);
        scanf("%d",&num);
        for(int i=0;i<num;i++) scanf("%d%d",&v[i],&w[i]);
        for(int i=0;i<year;i++)
        {
             for(int j=0;j<=sum/1000;j++) f[j]=0;
             for(int j=0;j<num;j++) zeroTwoPack(sum/1000,v[j]/1000,w[j]);
             sum+=f[sum/1000];
        }
        printf("%d\n",sum);
    }
    return 0;
}