0/1背包问题，递归求解，动态规划

朴素递归算法（时间超限）
参考代码:

1. #include <stdio.h>
   
   int t,m;
   
   typedef struct Item
   {
       int time;
       int val;
   }item;
   item a[101];
   
   int max(int a,int b)
   {
       return a>b?a:b;
   }
   
   int f(int i,int Capacity)
   {
       if(i==m)
           return (Capacity<a[i].time)?0:a[i].val;
       if(Capacity<a[i].time)
           return f(i+1,Capacity);
       return max(f(i+1,Capacity),f(i+1,Capacity-a[i].time)+a[i].val);
   }
   
   int main()
   {
       int i;
       scanf("%d %d",&t,&m);
       getchar();
   
   
       for(i=1;i<=m;i++)
       {
           scanf("%d %d",&a[i].time,&a[i].val);
           getchar();
       }
   
       int tval=f(1,t);
   
       printf("%d",tval);
   
       return 0;
   
   }

2.无重复计算的背包问题（正确），采用二维数组存储对应第几株草多少剩余时间的条件下的最优解（最大价值）

#include <stdio.h>
int t,m;
int ftmp[101][1001];

typedef struct Item
{
    int time;
    int val;
}item;
item a[101];

int max(int a,int b)
{
    return a>b?a:b;
}

int f(int i,int Capacity)
{
    if(ftmp[i][Capacity]>=0)
        return ftmp[i][Capacity];
    if(i==m)
        {
            ftmp[i][Capacity]=(Capacity<a[i].time)?0:a[i].val;
            return ftmp[i][Capacity];
        }
    if(Capacity<a[i].time)
        ftmp[i][Capacity]=f(i+1,Capacity);
    else
        ftmp[i][Capacity]=max(f(i+1,Capacity),f(i+1,Capacity-a[i].time)+a[i].val);

    return ftmp[i][Capacity];
}

int main()
{
    int i,j;
    scanf("%d %d",&t,&m);
    getchar();

    for(i=1;i<=m;i++)
        for(j=1;j<=t;j++)
            ftmp[i][j]=-1;

    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&a[i].time,&a[i].val);
        getchar();
    }
    int tval=f(1,t);

    printf("%d",tval);

    return 0;

}