2023年8月1日发(作者：)

算法训练-⼊学考试-C语⾔实现（⾠⾠是个天资聪颖的孩⼦，他的梦想是成为世界上最伟⼤的医师。。。。问题描述⾠⾠是个天资聪颖的孩⼦，他的梦想是成为世界上最伟⼤的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了⼀个难题。医师把他带到⼀个到处都是草药的⼭洞⾥对他说：“孩⼦，这个⼭洞⾥有⼀些不同的草药，采每⼀株都需要⼀些时间，每⼀株也有它⾃⾝的价值。我会给你⼀段时间，在这段时间⾥，你可以采到⼀些草药。如果你是⼀个聪明的孩⼦，你应该可以让采到的草药的总价值最⼤。”　　如果你是⾠⾠，你能完成这个任务吗？输⼊格式　　第⼀⾏有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），⽤⼀个空格隔开，T代表总共能够⽤来采药的时间，M代表⼭洞⾥的草药的数⽬。接下来的M⾏每⾏包括两个在1到100之间（包括1和100）的整数，分别表⽰采摘某株草药的时间和这株草药的价值。输出格式　　包括⼀⾏，这⼀⾏只包含⼀个整数，表⽰在规定的时间内，可以采到的草药的最⼤总价值。例⼦样例输⼊70 371 10069 11 2样例输出3思路经典01背包问题，求最⼤价值，动态规划，下⽂中定义的dp[i][j]代表的是当背包剩余容积为j，已经判定了i个物品时，背包的最优情况。代码呈上:#include #include #define max(x,y) (x>y)?x:yint main (){ int T,M,a,b; scanf("%d %d",&T,&M); int i,j; int dp[M+1][T+1]; memset(dp,0,sizeof(dp)); for(i=1;i<=M;i++) { scanf("%d %d",&a,&b); for(j=1;j<=T;j++) { if(j>=a) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b); else dp[i][j]=dp[i-1][j]; }

} printf("%d",dp[M][T]); return 0;}另⼀种写法：#include int T;int M;int dp[101][1001]={0};int t[101];int s[101];int main (){ scanf("%d %d",&T,&M); int i; t[0]=0; s[0]=0; for(i=1;ij) //时间不够

{ dp[i][j]=dp[i-1][j]; } else //时间够，但是看这个草药是采还是不采，选择⼤的

{ dp[i][j]=(dp[i-1][j-t[i]]+s[i])>(dp[i-1][j])?(dp[i-1][j-t[i]]+s[i]):(dp[i-1][j]); } } } printf("%d",dp[M][T]);

return 0;

}

运⾏⽰例

2023年8月1日发(作者：)

算法训练-⼊学考试-C语⾔实现（⾠⾠是个天资聪颖的孩⼦，他的梦想是成为世界上最伟⼤的医师。。。。问题描述⾠⾠是个天资聪颖的孩⼦，他的梦想是成为世界上最伟⼤的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了⼀个难题。医师把他带到⼀个到处都是草药的⼭洞⾥对他说：“孩⼦，这个⼭洞⾥有⼀些不同的草药，采每⼀株都需要⼀些时间，每⼀株也有它⾃⾝的价值。我会给你⼀段时间，在这段时间⾥，你可以采到⼀些草药。如果你是⼀个聪明的孩⼦，你应该可以让采到的草药的总价值最⼤。”　　如果你是⾠⾠，你能完成这个任务吗？输⼊格式　　第⼀⾏有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），⽤⼀个空格隔开，T代表总共能够⽤来采药的时间，M代表⼭洞⾥的草药的数⽬。接下来的M⾏每⾏包括两个在1到100之间（包括1和100）的整数，分别表⽰采摘某株草药的时间和这株草药的价值。输出格式　　包括⼀⾏，这⼀⾏只包含⼀个整数，表⽰在规定的时间内，可以采到的草药的最⼤总价值。例⼦样例输⼊70 371 10069 11 2样例输出3思路经典01背包问题，求最⼤价值，动态规划，下⽂中定义的dp[i][j]代表的是当背包剩余容积为j，已经判定了i个物品时，背包的最优情况。代码呈上:#include #include #define max(x,y) (x>y)?x:yint main (){ int T,M,a,b; scanf("%d %d",&T,&M); int i,j; int dp[M+1][T+1]; memset(dp,0,sizeof(dp)); for(i=1;i<=M;i++) { scanf("%d %d",&a,&b); for(j=1;j<=T;j++) { if(j>=a) dp[i][j]=max(dp[i-1][j],dp[i-1][j-a]+b); else dp[i][j]=dp[i-1][j]; }

} printf("%d",dp[M][T]); return 0;}另⼀种写法：#include int T;int M;int dp[101][1001]={0};int t[101];int s[101];int main (){ scanf("%d %d",&T,&M); int i; t[0]=0; s[0]=0; for(i=1;ij) //时间不够

{ dp[i][j]=dp[i-1][j]; } else //时间够，但是看这个草药是采还是不采，选择⼤的

{ dp[i][j]=(dp[i-1][j-t[i]]+s[i])>(dp[i-1][j])?(dp[i-1][j-t[i]]+s[i]):(dp[i-1][j]); } } } printf("%d",dp[M][T]);

return 0;

}

运⾏⽰例