采药 （C语言代码）

解题思路:
这道题提交了好多次都失败了，刚开始想当然地用贪心算法，后来发现错了又用回溯法，但是运行超时，最后采用动态规划顺利解决。这题的解题思路及方法其他题解已经讲得很清楚了。所以此文章仅仅是为了记下自己的代码便于日后自己复习。




注意事项:





参考代码

#include<stdio.h>
#if 0
void sort(int a[],int b[],int M); //贪心算法 
int main()
{
 int T,M;
 scanf("%d%d",&T,&M);
 int a[M],b[M];
 for(int i=0;i<M;i++)
  scanf("%d%d",&a[i],&b[i]);
 sort(a,b,M);
 int worth=0;
 for(int i=0;T>0&&i<M;i++)
  {
   if(a[i]<=T)
    {worth=worth+b[i]; 
     T=T-a[i];
    }
  }
  printf("%d",worth); 
  return 0;
 } 
void sort(int a[],int b[],int M)//按单位时间内价值大小按从大到小冒泡排序 
{
 if(M<=1)
  return ;
 for(int k=1;k<M;k++)
  for(int i=0;i<M-k;i++)
  
   if(((float)b[i])/a[i]<((float)b[i+1])/a[i+1])
    {
     int n;
     n=a[i];
     a[i]=a[i+1];
     a[i+1]=n;
     n=b[i];
     b[i]=b[i+1];
     b[i+1]=n;
    }  
 
}
/************************************************************/
int  max(int a,int b)      //回溯法 
{
 return a>b?a:b;
}
int solve(int a[],int b[],int T,int M)
{
 if(M==0)
  return 0;
 if(a[M-1]<=T)
  return max(solve(a,b,T-a[M-1],M-1)+b[M-1],solve(a,b,T,M-1));
 else return solve(a,b,T,M-1); 
}
int main()
{
  int T,M;
 scanf("%d%d",&T,&M);
 int a[M],b[M];
 for(int i=0;i<M;i++)
  scanf("%d%d",&a[i],&b[i]);
  printf("%d",solve(a,b,T,M));
 
}
#endif
/************************************************************/
int  max(int a,int b)           //动态规划 
{
 return a>b?a:b;
}
void solve(int matrix[101][1001],int a[],int b[],int M,int T)
{
 for(int m=1;m<=M;m++)
  for(int t=1;t<=T;t++)
   {
   if(a[m]<=t)
    matrix[m][t]=max(matrix[m-1][t-a[m]]+b[m],matrix[m-1][t]);
   else 
    matrix[m][t]=matrix[m-1][t];
   }  
}
int main()
{
  int T,M;
 scanf("%d%d",&T,&M);
 int a[M+1],b[M+1];
 for(int i=1;i<=M;i++)
  scanf("%d%d",&a[i],&b[i]);
 int matrix[101][1001];
 solve(matrix,a,b,M,T);
 printf("%d",matrix[M][T]); 
 
}

: