P1005 （C语言代码）

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define maxn 1001
#define MAX(a,b) a>b?a:b
int profit[maxn][maxn];

int Knapsack(int *time,int *value,int T,int M)//profit[i][j]表示前i个物品装到容量为j的背包中的最大收益
{
 for(int i=0;i <= M;i++)profit[i][0]=0;
 for(int i=0;i <= T;i++)profit[0][i]=0;
 for(int i=1;i <= M;i++)
 {
  for(int j=1;j <= T;j++)
  {
   if(j<time[i])
   {
    profit[i][j]=profit[i-1][j];
   }
   else
   {
    profit[i][j]=MAX(profit[i-1][j],profit[i-1][j-time[i]]+value[i]);
   }
  }
 }
 return profit[M][T];
}

int main()
{
 int T,M;//T代表总共用来采药的时间，M表示草药的数量
 scanf("%d %d",&T,&M);
 int *time = (int*)malloc(sizeof(int)*(M+1));
 int *value = (int*)malloc(sizeof(int)*(M+1));
 for(int i=1;i <= M;i++)scanf("%d %d",&time[i],&value[i]);
 printf("%d\n",Knapsack(time,value,T,M));
 free(value);
 free(time);
 return 0;
}