时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2705
解决：1311
- 题目描述：
-
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说：
“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
- 输入：
-
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
- 输出：
-
可能有多组测试数据，对于每组数据，
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
- 样例输入：
-
70 3
71 100
69 1
1 2
- 样例输出：
-
3
思路：
标准01背包问题。
此类问题同时也可以用递归DFS来解，我当时用的是DFS，见代码1。
别人写的01背包解法见代码2。
代码1：
#include <stdio.h> #define T 1000
#define M 100 int at[M], am[M];
int v[T][M]; int value(int tt, int mm)
{
if (mm == 0)
{
if (at[mm] <= tt)
return am[mm];
else
return 0;
}
int value1, value2;
if (v[tt][mm-1] != -1)
value1 = v[tt][mm-1];
else
{
value1 = value(tt, mm-1);
v[tt][mm-1] = value1;
}
if (at[mm] > tt)
{
//printf("tt=%d, mm=%d, value1=%d\n", tt, mm-1, value1);
return value1;
}
else
{
if (v[tt-at[mm]][mm-1] != -1)
value2 = am[mm] + v[tt-at[mm]][mm-1];
else
{
value2 = value(tt-at[mm], mm-1);
v[tt-at[mm]][mm-1] = value2;
value2 += am[mm];
}
//printf("am[mm]=%d, tt=%d, mm=%d, value2=%d\n", am[mm], tt-at[mm], mm-1, value2);
return value1>value2 ? value1 : value2;
}
} int main(void)
{
int t, m;
int i, j; while (scanf("%d%d", &t, &m) != EOF)
{
for (i=0; i<m; i++)
scanf("%d%d", &at[i], &am[i]); for (i=0; i<T; i++)
{
for (j=0; j<M; j++)
{
v[i][j] = (i==0) ? 0 : -1;
}
}
printf("%d\n", value(t, m-1));
} return 0;
}
/**************************************************************
Problem: 1123
User: liangrx06
Language: C
Result: Accepted
Time:520 ms
Memory:1304 kb
****************************************************************/
代码2：
#include<stdio.h>
#include<stdlib.h> int max2int(int a,int b)
{
if(a>b)
{
return a;
}
return b;
}
int getmaxvalue(int* the_time,int* values,int num,int totaltime)
{
/*输入 the_time是每一项的时间
* values是每一项的价值
* num是总的项数
* totaltime是最大可用时间
*
* 输出为能够取到的最大值
* */ int* ans=(int*)malloc((totaltime+1)*sizeof(int));
int i,j,maxvalue; for(i=0;i!=(totaltime+1);i++)
{
ans[i]=0;
} for(i=0;i!=num;i++)
{
for(j=totaltime;j>=0;j--)
{
if(j-the_time[i]>=0)
{
ans[j]=max2int(ans[j],ans[j-the_time[i]]+values[i]);
}
}
} maxvalue=ans[totaltime];
free(ans);
return maxvalue;
}
int main(int argc,char** argv)
{
int *the_time,*values,t,m,i; while(scanf("%d%d",&t,&m)!=EOF)
{
the_time=(int*)malloc(m*sizeof(int));
values=(int*)malloc(m*sizeof(int)); for(i=0;i<m;i++)
{
scanf("%d%d",the_time+i,values+i);
}
printf("%d\n",getmaxvalue(the_time,values,m,t)); free(the_time);
free(values);
}
return 0;
}
/**************************************************************
Problem: 1123
User: liangrx06
Language: C
Result: Accepted
Time:100 ms
Memory:912 kb
****************************************************************/