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

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

参考代码:

#include <bits/stdc++.h>
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;j<=t;j++){//j为时间   时间不断增加 
            if(t1[i]>j) {//如果选择这个药材需要的时间大于现在有的时间，那么这个药材就不能选择 
                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<=m;i++){
        cin>>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<=m;i++){
            cin>>t1[i]>>val[i];
        }
	way();
	cout<<dp[m][t];
}
int main(){
	solve();
	return 0;
}