采药 刷题笔记 （动态规划）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;
} 

另一个0/1背包 供参考

01背包问题 刷题笔记_背包问题中字母表示什么-CSDN博客

原文地址：https://blog.csdn.net/2301_78763076/article/details/144226200

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！