1100: 采药（C++）

解题思路:    本题是01背包类型的题目，无法通过排序的方法来简化比较过程，故采用二维数组动态规划的办法解题.

参考代码:

//采药
#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

int main(){
// T（1 <= T <= 1000）和M（1 <= M <= 100）   总共能够用来采药的时间(T)，山洞里的草药的数目(M) -->背包容量T,单位物体总数M(用于控制输入)
// 后M行各有两个整数t,v（1<=t,v<=100），分别表示采摘某株草药的时间(t)和这株草药的价值(v)-->单位物体的占用容量t,单位物体价值v
    int T,M;
    cin >> T >> M;
    vector <int> t;
    vector <int> v;
    for (int i = 0; i < M; i++) {
        int in1,in2;
        cin >> in1 >> in2;
        t.push_back(in1);
        v.push_back(in2);
    }

//  dp二维数组   n1：限定递归的总数，给定上限；v1：为一维数组（n2:限定递归的总容量；v2:最大价值数）,(T+1,0)是指
//  每个vector<int>元素都被初始化为一个大小为T+1的vector，并且所有元素的初始值都是0
    vector <vector<int>> dp (M,vector<int>(T+1,0));//T+1是由于容量需要从0开始考虑

//    初始化二维数组的价值
    for (int j = t[0]; j < T; j++) {
        dp[0][j]=v[0];
    }

    for (int i = 1; i < M; i++) {//遍历总个数
        for (int j = 0 ; j < T+1;j++){//遍历容量
            if (j < t[i])   dp[i][j]=dp[i-1][j];
//          剩余容量j小于待加入的单位物体占用容量t[i]的情况直接同理总数少的情况，即无视该物体，最大价值同总个数更小的情况
            else dp[i][j] = max(dp[i-1][j], dp[i - 1][j - t[i]] + v[i]);
//          剩余容量j大于……的情况下，总数确定，总容量减少某种单位物体容量但总价值增加的情况与同总个数更小的情况做对比，取更大价值
//          如果剩余容量足够就进行比较再决定放入的总价值数，放入总价值数为总数确定且容量确定情况下总价值的最大价值数
        }
    }
//   这里遍历的顺序是可以交换的，不过习惯上按照二维数组元素类型顺序进行遍历

    cout << dp[M - 1][T] << endl;
//    经过二维的递归遍历比较后，最后比较获得的最大价值数即为所求
}