采药 （C++代码）

解题思路:01背包问题  本质是建一个 药的序号和时间 的二维数组  写入每一个元素时都分为采与不采这个药  这两种情况得到总价值的最优解就是本元素的值 由于写入一个元素是需要用到前面的元素,故次数组要从开始建立  

注意事项: 注意数组大小 按照代码 自己写一个简单例子在纸上写出二维数组 就能理解

参考代码:

#include<iostream>

using namespace std;

int main()

{

    int T,M;

    cin>>T>>M;

    int time[101]= {0};

    int value[101]= {0};

    int i;

    for(i=1; i<=M; i++)

    {

        cin>>time[i]>>value[i];

    }

    int m[101][1001]= {0};

    for(int i=1; i<=M; i++)

    {

        for(int j=1; j<=T; j++)

        {

            if(j>=time[i])

            {

                m[i][j]=max(m[i-1][j],m[i-1][j-time[i]]+value[i]);

            }

            else

            {

                m[i][j]=m[i-1][j];

            }

        }

    }

    cout<<m[M][T]<<endl;

    return 0;

}