采药 （C++代码）DP（动态规划）

解题思路:

    标准的01背包问题。
参考代码:

#include<iostream>
#include<cmath>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int Value_max=1005;
const int Time_max=105;

int dp[Time_max][Value_max]= {0};	//动态规划 
int value[Value_max]= {0};	//价值 
int cost[Time_max]= {0};	//耗时 

int total_time;	//总时间 
int n;			//总药品的数量 

void knapsack() {	//01背包算法 
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=total_time; j++) {
			if(cost[i]>j) {
				dp[i][j]=dp[i-1][j]; 
			} else {
				dp[i][j]=max(dp[i-1][j-cost[i]]+value[i],dp[i-1][j]);
			}
		}
	}
}

int main() {
	hh;
	cin>>total_time>>n;
	for(int i=1; i<=n; i++) {
		cin>>cost[i]>>value[i];
	}
	knapsack();
	cout<<dp[n][total_time]<<endl;
	return 0;
}

代码更新：

01背包的标准可以参照本题目的优质题解，然而，01背包是可以压缩空间的，即使用一维数组替代二维的效果，以下为代码。

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int maxn=100005;
int w[maxn]={0},v[maxn]={0};
int dp[maxn]={0};
int weight,value,n;
int main(){
	hh;
	cin>>weight>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=weight;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[weight]<<endl;
	return 0;
}