采药——北京大学【01背包模板题】

文章目录

• 题目描述
• 知识点
• 实现
• • 码前思考
  • 代码实现
  • 码后反思

题目描述

知识点

naked 0-1背包问题

实现

码前思考

1. 虽然很久没写过背包了，但是这个看起来还有一点印象，所以写的还是蛮快的。
2. 关于这个题目中如何设置状态数组，我想起了之前看的一篇微信公众号写的文章

1. 你首先看这个问题可不可以用递归进行实现？显然我们这个题目可以使用递归进行实现，设f的意义为在规定质量最大为w的情况下，前i件商品能实现的最大价值。
2. 然后将递归的函数f转换成状态数组dp，然后进行递推就行。

代码实现

//数组下标从1开始 
#include "bits/stdc++.h"
using namespace std;const int maxt = 1010;
const int maxm = 110;//价值数组
int v[maxm];
//时间数组
int t[maxm];
//dp数组
int dp[maxm][maxt];//输入的总时间
int T;
//输入的草药数
int m;int main(){while(~(scanf("%d%d",&T,&m))){//读入数据 for(int i=1;i<=m;i++){scanf("%d %d",&t[i],&v[i]); }//动态规划的递推边界for(int i=0;i<=T;i++){dp[0][i] = 0;}//开始进行动态规划for(int i=1;i<=m;i++){for(int j=0;j<t[i];++j){dp[i][j] = dp[i-1][j];}for(int j=t[i];j<=T;++j){dp[i][j] = max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);}}printf("%d\n",dp[m][T]); }return 0;
} 

码后反思

1. 其实0-1背包还可以继续优化dp数组，考虑到dp[i][j]只与dp[i-1][j]和dp[i-1][j-t[i]]有关，因此我们可以把其变成1维的:

//数组下标从1开始 
#include "bits/stdc++.h"
using namespace std;const int maxt = 1010;
const int maxm = 110;//价值数组
int v[maxm];
//时间数组
int t[maxm];
//dp数组
int dp[maxt];//输入的总时间
int T;
//输入的草药数
int m;int main(){while(~(scanf("%d%d",&T,&m))){//读入数据 for(int i=1;i<=m;i++){scanf("%d %d",&t[i],&v[i]); }//动态规划的递推边界for(int i=0;i<=T;i++){dp[i] = 0;}//开始进行动态规划for(int i=1;i<=m;i++){for(int j=T;j>=t[i];j--){dp[j] = max(dp[j],dp[j-t[i]]+v[i]);}}printf("%d\n",dp[T]); }return 0;
}