P1616 疯狂的采药(完全背包）

//https://www.luogu.com.cn/problem/P1616
//完全背包问题
#include<bits/stdc++.h>
using namespace std;
int T,m;
long long t[10001];
long long value[10001];
//long long dp[10001][10001];
long long dp[10000001];
int main()
{
   cin>>T>>m;
   for(int i=1;i<=m;i++)
   {
       cin>>t[i];
       cin>>value[i];
   }
   //背包初始化化
//    for(int i=1;i<=m;i++)
//        dp[0][i]=0;
//    for(int i=1;i<=m;i++)
//        for(int j=1;j<=T;j++)
//        {
//            if(j>=t[i])//注意一定要有等号啊-----等于也是可以采的
//            {
//                dp[i][j]=max(dp[i][j-t[i]]+value[i],dp[i-1][j]);
//            }
//            else
//                dp[i][j]=dp[i-1][j];
//        }
//    cout<<dp[m][T];
//   for(int i=1;i<=m;i++)
//   {
//       for (int j = 1; j <= T; j++)
//       {
//           printf("%d ", dp[i][j]);
//       }
//       printf("\n");
//   }
//        return 0;
       //采用二维数组的完全背包已经超出内存限制了，故使用一维滚动数组实现背包
       //初始化
       for(int i=1;i<=m;i++)
           dp[i]=0;
       for(int i=1;i<=m;i++)
           for(int j=1;j<=T;j++)//完全背包一维情况要正序枚举背包容量已提供充足的信息
           {
               if(j>=t[i])
                   dp[j]=max(dp[j],dp[j-t[i]]+value[i]);
               else
                   dp[j]=dp[j];
           }
       cout<<dp[T];
           return 0;
}