[编程题]采药
- 热度指数：11767 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。
为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。
医师把他带到个到处都是草药的山洞里对他说：
“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入描述:
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。 接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出描述:
可能有多组测试数据，对于每组数据， 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
示例1
输入
70 3 71 100 69 1 1 2
输出
3
是北大点菜的那个辰辰吗？
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int t=sc.nextInt();
int m=sc.nextInt();
int []time=new int[m];
int []value=new int[m];
for(int i=0;i<m;i++) {
time[i]=sc.nextInt();
value[i]=sc.nextInt();
}
int []dp=new int[t+1];//针对时间
for(int i=0;i<m;i++) {//针对每个草药
for(int j=t;j>=time[i];j--) {
dp[j]=Math.max(dp[j], dp[j-time[i]]+value[i]);
}
}
System.out.println(dp[t]);
}
}
}
发表于 2020-04-13 07:37:08
回复(2)
#include <stdio.h>
struct hert{
int time;
int value;
}hert[101];
int dp[1001];
int max(int i,int j)
{
return (i>j)?i:j;
}
int main()
{
int T,N;
while(scanf("%d%d",&T,&N)!=EOF)
{
for(int i=1;i<=N;i++)
{
scanf("%d%d",&hert[i].time,&hert[i].value);
}
for(int i=0;i<=T;i++)
{
dp[i]=0;
}
for(int i=1;i<=N;i++)
{
for(int j=T;j>=hert[i].time;j--)
{
dp[j]=max(dp[j],dp[j-hert[i].time]+hert[i].value);
}
}
printf("%d\n",dp[T]);
}
return 0;
}
发表于 2017-09-07 21:55:17
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int M = 1001;
int val[M], time_cost[M]; //存储给定草药的价值和花费时间
int f[M][M]; //第一维坐标表示对于第i个草药的取舍，第二维坐标表示所花费时间
//经典01背包，然而我只会用二维矩阵，令人感叹
int main (){
int t1me, m;
while (~ scanf ("%d %d", &t1me, &m)){
for (int i = 1; i <= m; ++ i) scanf ("%d %d", &time_cost[i], &val[i]);
for (int i = 1; i <= m; ++ i){
for (int j = 1; j <= t1me; ++ j){
f[i][j] = f[i - 1][j]; //首先默认舍去第i个草药
if (j >= time_cost[i]){ // 如果当前时间不够采集第i个草药则跳过
f[i][j] = max(f[i][j], f[i - 1][j - time_cost[i]] + val[i]);
//在时间为j，考虑前i个草药的条件下，最大的值为f[i][j]
}
}
}
cout << f[m][t1me] << endl;
}
return 0;
}
发表于 2022-03-11 11:29:20
回复(0)
//背包问题, 在把包装满的前提下求最大价值也就是最优解
#include<stdio.h>
int max(int a,int b){return a>b?a:b;}
struct beibao{
int time;
int value;
}num[100];
int main()
{ //n目标时间t药的种类
int dp[1001],n,t,i,j;//dp[n]即时间为n时候的价值
while(scanf("%d%d",&n,&t)!=EOF)
{
for(i=0;i<t;i++)//输入
scanf("%d%d",&num[i].time,&num[i].value);
for(int i=0;i<=n;++i)
dp[i]=0;//初始化
for(i=0;i<t;i++)//每个药
for(j=n;j>=num[i].time;j--)
dp[j]=max(dp[j-num[i].time]+num[i].value,dp[j]);//要最大价值
printf("%d\n",dp[n]);
}
}
发表于 2020-04-03 16:59:53
回复(0)
/*
动态规划，01背包
状态表示，f[i]表示i时间所能采摘的最大的价值
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int t,m;
int v[maxn],w[maxn];
int f[maxn];
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++) cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)
for(int j=t;j>=v[i];j--)
f[j] = max(f[j],f[j-v[i]]+w[i]);
cout<<f[t]<<endl;
}
发表于 2020-03-24 20:13:16
回复(0)
C++版本：
#include<iostream>
#include<algorithm>
using namespace std;
int **dp;//【index_of_medicine，remainning_time】
int m;// nums of med.
int *w;// costs of med.
int *v;// values of med.
int f(int i,int t){//i:第i个草药。t：剩余的时间
int res;
if(dp[i][t]>0)
return dp[i][t];
if(i==m)
res = 0;
else if(w[i]>t)
res = f(i+1,t);
else
res = max(f(i+1,t),f(i+1,t-w[i])+v[i]);
return dp[i][t] = res;
}
int main(){
int t;
while(cin>>t>>m){
dp = new int*[m+1];
for(int i=0;i<m+1;i++) dp[i] = new int[t+1];
for(int i=0;i<m+1;i++)
for(int j=0;j<t+1;j++){
dp[i][j] = 0;
}
w = new int[m];
v = new int[m];
for(int i=0;i<m;i++){
scanf("%d %d",&w[i],&v[i]);
}
cout<<f(0,t)<<endl;
}
return 0;
}
编辑于 2019-01-27 18:04:48
回复(0)
动态规划，用一个数组values[i]表示i时间能采集到的草药价值
如果比所给时间小，从后往前到不够时间摘下该草药为止，看加入进来是否有价值增加的可能。
while True:
try:
t,m = list(map(int,input().split()))
selects = []
for i in range(m):
selects.append(list(map(int,input().split())))
values = [0] * (t+1)
for i in range(m):
if selects[i][0] <= t:
for j in range(t,selects[i][0]-1,-1):
values[j] = max(values[j],values[j-selects[i][0]]+selects[i][1])
print(values[t])
except Exception:
break
编辑于 2018-10-01 17:14:53
回复(0)
0-1背包问题：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int T = in.nextInt();
int M = in.nextInt();
int[][] arr = new int[M+1][2];
for(int i=1;i<=M;i++){
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
int[][] dp = new int[M+1][T+1];
for(int i=0;i<=T;i++){
dp[0][i]=0;
}
for(int i=1;i<=M;i++){
for(int j=0;j<=T;j++){
if(j<arr[i][0])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-arr[i][0]] + arr[i][1]);
}
}
System.out.println(dp[M][T]);
}
}
}
发表于 2018-02-13 15:56:29
回复(0)
#include<stdio.h>
#define MAX(a,b) (a>b?a:b)
int dp[1001];
char t[101], v[101];
int main() {
int T, M;
while (~scanf("%d%d", &T, &M)) {
for (int i = 0; i < M; i++)scanf("%d%d", t + i, v + i);
for (int i = 0; i <= T; i++)dp[i] = 0;
for (int i = 0; i < M; i++)
for (int j = T; j >= t[i]; j--)
dp[j] = MAX(dp[j - t[i]] + v[i], dp[j]);
printf("%d\n", dp[T]);
}
return 0;
}
发表于 2017-03-07 00:46:56
回复(0)
0-1背包问题
#include <stdio.h>
int max(int a,int b){return a>b?a:b;}struct medicine{
int s;
int v;
}list[101];
int dp[1001];
int main(){
int n,s; //n为时间，s为药的种类
while(scanf("%d%d",&n,&s)!=EOF){
for(int i=1;i<=s;++i)
scanf("%d%d",&list[i].s,&list[i].v);
for(int i=0;i<=n;++i)dp[i]=0;
for(int i=1;i<=s;++i)
for(int j=n;j>=list[i].s;j--)
dp[j]=max(dp[j-list[i].s]+list[i].v,dp[j]);
printf("%d\n",dp[n]);
}
return 0;
}
发表于 2018-01-27 16:33:48
回复(0)
1. 回溯法 + 备忘录
对于每一个物品都有两种选择： 选 or 不选，于是在处理 物品总重量时 max( W - wt[i] + val[i], W)，然后继续往后选择
int backTrack(int W, int i, int N, vector<int>& wt, vector<int>& val, vector<vector<int>>& memo) {
if (W == 0 || i == N + 1) return 0;
if (memo[i][W] != -1) return memo[i][W];
int subProb1 = 0;
if (W >= wt[i])
subProb1 = backTrack(W - wt[i], i + 1, N, wt, val, memo) + val[i];
int subProb2 = backTrack(W, i + 1, N, wt, val, memo);
memo[i][W] = max(subProb1, subProb2);
return memo[i][W];
} 横坐标是物品的 index( 0 -> N )，纵坐标是 w ( 0 -> W) 按照 -> 这个方向遍历，填补
int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
for (int n = 1; n <= N; n++)
for (int w = 1; w <= W; w++)
{
if (wt[n] <= w)
dp[n][w] = max(dp[n - 1][w - wt[n]] + val[n], dp[n - 1][w]);
else
dp[n][w] = dp[n - 1][w];
}
return dp[N][W];
}
发表于 2023-05-04 09:00:52
回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t,m;
while(cin>>t>>m){
vector<vector<int>>herb(m,vector<int>(2));
vector<int>dp(t+1,0);
for(int i=0;i<m;i++){
cin>>herb[i][0]>>herb[i][1];
}
for(int i=0;i<m;i++){
for(int j=t;j>=herb[i][0];j--){
dp[j]=max(dp[j],dp[j-herb[i][0]]+herb[i][1]);
}
}
cout<<dp[t]<<endl;
}
}
发表于 2025-03-24 10:56:53
回复(0)
经典01背包
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, m;
cin >> t >> m;
vector<int> value(m), weight(m);
for (int i = 0; i < m; i++) {
cin >> weight[i] >> value[i];
}
vector<int> dp(t + 1, 0);
// 01背包
for (int i = 0; i < m; i++) { // 物品
for (int j = t; j >= weight[i]; j--) { // 背包重量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[t];
return 0;
}
发表于 2024-03-21 13:49:41
回复(0)
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int dp[1020],mv[120],mcost[120];
int t,m;
while(cin>>t>>m){
for(int i=0;i<m;i++){
cin>>mcost[i]>>mv[i];
}
memset(dp, 0, sizeof(dp));
for(int i=0;i<m;i++){
for(int j=t;j>=mcost[i];j--){
dp[j]=max(dp[j],dp[j-mcost[i]]+mv[i]);
}
}
cout<<dp[t]<<endl;
}
}
//和KY66点菜问题感觉基本一样
发表于 2023-03-22 15:33:23
回复(0)
//经典的0-1背包问题
#include "stdio.h"
#include "algorithm"
using namespace std;
int T,M;//T为总时间，M为草药株树
int plantTime[110];
int val[110];
int bag[110][1010];
void Init(){//构造背包的动态规划二维数组
for (int i = 0; i <= M; ++i) {
for (int j = 0; j <= T; ++j) {
if(i == 0 || j == 0){
bag[i][j] == 0;
continue;
}
if(plantTime[i] > j){
bag[i][j] = bag[i-1][j];
} else{
bag[i][j] = max(bag[i-1][j],bag[i-1][j-plantTime[i]]+val[i]);
}
}
}
}
int main(){
while (scanf("%d%d",&T,&M)!=EOF){
for (int i = 1; i <= M; ++i) {
scanf("%d%d",plantTime+i,val+i);
}
Init();
printf("%d\n",bag[M][T]);
}
}
发表于 2023-03-10 19:37:23
回复(0)
//ky75
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1010;
int weight[MAXN],value[MAXN];
int dp[MAXN][MAXN];
int main(){
int T,M;
while(scanf("%d %d",&T,&M)!=EOF){
for(int i=1;i<=M;i++){
scanf("%d %d",&weight[i],&value[i]);
}
for(int i=0;i<=T;i++){
dp[0][i]=0;
}
for(int i=0;i<=M;i++){
dp[i][0]=0;
}
for(int x=1;x<=T;x++){
for(int y=1;y<=M;y++){
if(x<weight[y])
dp[y][x]=dp[y-1][x];
else
dp[y][x]=max(dp[y-1][x],dp[y-1][x-weight[y]]+value[y]);
}
}
printf("%d\n",dp[M][T]);
}
}
发表于 2022-03-10 19:41:22
回复(0)
while True: try: T, M = [int(i) for i in input().split()] values = [[] for i in range(M)] for i in range(M): values[i] = [int(i) for i in input().split()] dp = [[0 for i in range(T+1)] for _ in range(M+1)] for i in range(1, M + 1): for j in range(1, T + 1): #这里的i-1是因为我们的价值矩阵values从0开始索引的，不是代表第0件物品，注意细节 if j - values[i - 1][0] >= 0: value_with_i = values[i - 1][1] + dp[i-1][j - values[i - 1][0]] else: value_with_i = 0 value_without_i = dp[i - 1][j] dp[i][j] = max(value_with_i, value_without_i) print(dp[-1][-1]) except: break
发表于 2022-03-09 21:35:47
回复(0)
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1000 + 10;
int main(){
int t, m, weight[N], value[N], dp[N];
while(scanf("%d%d", &t, &m) != EOF){
for(int i = 0; i < m; i++) scanf("%d%d", &weight[i], &value[i]);
fill(dp, dp + t + 1, 0);
for(int i = 0; i < m; i++){
for(int j = t; j >= weight[i]; j--)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
printf("%d\n", dp[t]);
}
return 0;
}
发表于 2022-03-01 10:05:40
回复(0)
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int n, m;
int main(){
while(cin >> m >> n){
for(int i = 0, v, w; i < n; i ++ ){
cin >> v >> w;
for(int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
}
return 0;
}
发表于 2021-08-04 20:29:50
回复(0)
问题信息
难度：
66条回答
151收藏
9888浏览
通过挑战的用户
查看代码-
2023-03-14 17:32:27
-
2023-03-14 11:29:53 -
2023-03-13 09:48:26 -
2023-03-11 10:46:07
-
2023-03-07 22:47:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
