原题链接：采药
解题思路:
根据回溯法，首先画出解空间，解空间就是按照深度优先遍历的得到最优解的叉树（不一定是二叉树）
注意事项:
回溯超时，别提交；
参考代码:
#include <stdio.h>
int T, m, time[101], value[101], pvalue = 0, maxvalue = 0;
int tanxin( int i );
void function( int i );
/*-----------------------------------------------------*/
int main()
{
while ( (scanf( "%d%d", &T, &m ) ) != EOF )
{
maxvalue = 0;
pvalue = 0;
for ( int i = 0; i < m; i++ )
scanf( "%d%d", &time[i], &value[i] );
function( 0 );
printf( "%d\n", maxvalue );
}
}
/*-----------------------------------------------------*/
void function( int i )
{
if ( i >= m )
{
if ( maxvalue < pvalue )
{
maxvalue = pvalue;
}
return;
}
if ( T >= time[i] )
{
pvalue += value[i];
T -= time[i];
function( i + 1 );
pvalue -= value[i];
T += time[i];
}
if ( tanxin( i + 1 ) > maxvalue )
function( i + 1 );
return;
}
int tanxin( int i )
{
int left = T;
int b = pvalue;
while ( i <= m && time[i] <= T )
{
left -= time[i];
b += value[i];
i++;
}
if ( i <= m )
b += value[i] * (1.0 * left / time[i]);
return(b);
}0.0分
11 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
#include<stdio.h> int main() { int t,m,t1=0; scanf("%d %d",&t,&m); int i,p; int a[100],b[100]; float c[100],o; int b1=0; for(i=0;i<m;i++) { scanf("%d %d",&a[i],&b[i]); c[i]=b[i]*1.0/a[i]*1.0; } for(i=0;i<m;i++) { for(p=i;p<m;p++) { if(c[i]<c[p]) { o=c[i]; c[i]=c[p]; c[p]=o; o=a[i]; a[i]=a[p]; a[p]=o; o=b[i]; b[i]=b[p]; b[p]=o; } } } for(i=0;i<m;i++) { if((t1+a[i])>t) { continue; } t1=t1+a[i]; b1=b1+b[i]; } printf("%d",b1); }动态规划，简单的背包问题 import java.util.*; public class Main { static Scanner sc=new Scanner(System.in); static final int N=1010; static int []f=new int[N]; static int []v=new int[N]; static int []w=new int[N]; public static void main(String[] args) { int m=sc.nextInt(),n=sc.nextInt(); for(int i=1;i<=n;i++) { v[i]=sc.nextInt(); w[i]=sc.nextInt(); } for(int i=1;i<=n;i++) { for(int j=m;j>=v[i];j--) { f[j]=Math.max(f[j], f[j-v[i]]+w[i]); } } System.out.println(f[m]); } }动态规划01背包 #include <stdio.h> #define Max 1001 int f[Max][Max]={0}; int price[Max]={0}; int time[Max]={0}; int B(int k,int t) { for(int i=1;i<=k;i++) { for(int j=1;j<=t;j++) { if(time[i]>j) f[i][j]=f[i-1][j]; else { int a=f[i-1][j]; int b=f[i-1][j-time[i]]+price[i]; if(a>=b) f[i][j]=a; else f[i][j]=b; } } } printf("%d\n",f[k][t]); } int main() { int T,M; scanf("%d%d",&T,&M); for(int i=1;i<=M;i++) scanf("%d%d",&time[i],&price[i]); B(M,T); return 0; } /* 50 5 20 10 30 5 40 18 20 9 10 12 */同样是超时 囧 #include<stdio.h> #include<string.h> struct node{ int a,b; }; typedef struct node list; list A[105]; list s; int sum,k; int T,M; void jisuan(int star,list s ){ if(star==k){ if(s.b>sum){ sum=s.b; } return; } int i; int x=s.a; int y=s.b; //printf("s.a=%d\n",y); for(i=star;i<k;i++){ s.a+=A[i].a; if(s.a<=T){ s.b+=A[i].b; //printf("s.b=%d\n",s.b ); if(s.b>sum){ sum=s.b; //printf("sum=%d\n",sum); } jisuan(i+1,s); } s.a=x; s.b=y; } } int main(){ while(scanf("%d %d",&T,&M)!=EOF){ int i,t1,t2; k=0; sum=0;我也是超时，不过你的代码看起来逻辑性太差~ #include<stdio.h> int max(int a,int b) { return a>b?a:b; } int solve(int a[],int b[],int T,int M) //函数功能：a数组存储M种药的采药时间，b数组存储M种药的价值，M表示剩下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)); }