采药---类似背包，详细注释

详细注释的代码，解释背包原理

参考代码:

#include using namespace std;
const int N = 1000 + 50;
int t1[N],val[N];//t1[i] 表示编号为i的药材所需要的时间，val[i]表示的是编号为i的药材价值 
int dp[N][N];//行表示待选个体的编号(从1开始)，列表示限制条件的大小 
//对于背包问题，行就是选择要装的东西编号，列就是
// 枚举的背包体积，而此题的行就是待选药材的编号，列就是时间的枚举 

int t,m;//t记录总时间和  m 记录待选药材数 
void way(){//处理dp数据 ，dp数组初始化为0
//dp[i][0] = 0;表示的是时间为0时 从编号为前i的所有药材中选出满足条件的(整体价值最大)
//显然时间为0时所有药材都无法放入，故其最大价值为0
//dp[0][i] = 0;表示没有待选药材，无论时间有多少，没有药材那么他的最大价值也为0 
	for(int i=1;i<=m;i++){//从加入第一个待选药材起 遍历完善 不同时间下的最大价值 
		for(int j=1;jj) {//如果选择这个药材需要的时间大于现在有的时间，那么这个药材就不能选择 
				dp[i][j] = dp[i-1][j];//那么这个条件下的最大值就是相同时间下前i-1个编号的最大值 
			}
			else{//现在有的时间充足，可以选择这个药材
			//可以选择不等于一定选择，可能因为选择了他而导致时间不够而放弃
			//选择在此编号之前更有价值的药材 (要把时间给到更有价值的药材上)
			//因此可以选择  又有 选 和 不选 两种情况 
			//dp[i-1][j]表示如果不选情况和上面一致  此时最大值就是相同时间下前i-1个编号的最大值 
			//dp[i-1][j-t1[i]] + val[i] 如果选上，就要给他预留时间(t1[i])， 
			//在其余时间(j-t1[i])里去从i-1个药材种选出最大价值，再加上这个药材有的价值 
			//在二者中选出最大值 
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-t1[i]] + val[i]);
			}
		}
	}
}
void solve(){//数据初始化 
	cin>>t>>m;
	memset(dp,0,sizeof(dp));
	memset(t1,0,sizeof(t1));
	memset(val,0,sizeof(val));
	for(int i=1;i>t1[i]>>val[i];
	}
	way();
	cout<<dp[m][t];//直接输出在总时间t下，i个药材的最大价值 
}
int main(){
	solve();
	return 0;
}

简介代码：

#include using namespace std;
const int N = 1000 + 50;
int t1[N],val[N];
int dp[N][N];
int t,m;
void way(){
	for(int i=1;i<=m;i++){
		for(int j=1;jj) dp[i][j] = dp[i-1][j];
			else{
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-t1[i]] + val[i]);
			}
		}
	}
}
void solve(){
	cin>>t>>m;
	memset(dp,0,sizeof(dp));
	memset(t1,0,sizeof(t1));
	memset(val,0,sizeof(val));
	for(int i=1;i>t1[i]>>val[i];
	}
	way();
	cout<<dp[m][t];
}
int main(){
	solve();
	return 0;
}