采药刷题笔记（动态规划）0/1背包

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态

动态规划

0/1背包的本质在于继承

一行一行更新

上一行是考虑前i个物品的最优情况

当前行是考虑第i+1个物品的情况当前行的最优解来自上一行和前i个物品的最优解进行比较如果当前装了当前物品（第i +1个物品）的情况更优则将当前行更新

否则直接从上一行进行继承

dp[i][j]表示时间为j的情况下装前i个物品的最优解

dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i+1]]+value[i+1]]

继承过程

再举个例子输入

25 5

8 25

3 4

9 36

2 6

1 2

代码

#include<iostream>
#include<math.h>
#include<algorithm>
const int N=110;
using namespace std;
int t[N],v[N]; //t 数组存采摘所需时间 v数组存草药价值
int dp[N][1100];

int main(){
   int maxtime,num;
   cin>>maxtime>>num;
   for(int i=1;i<=num;i++){
       cin>>t[i]>>v[i];
   }

   for(int i=1;i<=num;i++){
   //   cout<<t[i]<<' '<<v[i]<<endl;
   }
   for(int i=1;i<=num;i++){
       for(int j=1;j<=maxtime;j++){
           if(t[i]<=j){
               dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
           } else{
               dp[i][j]=dp[i-1][j];
           }

       }
   }
   for(int i=1;i<=num;i++){
       for(int j=1;j<=maxtime;j++){
       //   cout<<dp[i][j]<<' ';

           //cout<<j<<' ';
       }
       //cout<<endl;
   }

   cout<<dp[num][maxtime];




   return 0;
}