B1778 采药

【分析】

$01$ 背包问题，时间 $t$ 为总容积， 每行的两个数代表了 $w$ 和 $v$ ，是采摘每个药的时间和价值，也就是每个物品的体积和价值。

也就是求 $m$ 个物品，再容积为 $t$ 的情况下的最大价值。

#include <bits/stdc++.h>
using namespace std;
/**
01 背包问题 
时间 t 为总容积， 每行的两个数代表了 w 和 v 
*/ 
int dp[110][1010]; // dp[i][j] 存储前 i 个物品在 j的的容积下的最大价值 
int main(){
	int t, m, w, v;
	cin >> t >> m;
	for (int i = 1; i <= m; i++){//m个物品 
		cin >> w >> v;//输入每个物品的体积和价值(时间、价值）
		for (int j = 1; j <= t; j++){
			if (j < w){
				dp[i][j] = dp[i-1][j];
			} else {
				dp[i][j] =  max(dp[i-1][j], dp[i-1][j-w] + v);
			}
		}
	} 
	cout << dp[m][t];
	return 0;
}

时间复杂度为： $O(mT)$ ， 即 $O(n^)$。

【优化】一维数组优化

• 对于第 $i$ 个物品， 当 $j < w$ 时，第 $i$ 个物品并不能被选择, $dp[i][j]$ 直接从上一层的状态 $dp[i - 1][j]$ 转移而来。
• 当 $j ≥ w$ 时，可以选择第 $i$ 个物品, 此时 $dp[i][j]$ 直接从上一层的状态 $dp[i - 1][j]$ 以及 $dp[i - 1][j - w] + v$转移而来。

所以可以采用一维数组优化

#include <bits/stdc++.h>
using namespace std;
/**
01 背包问题 :一维数组优化 
时间 t 为总容积， 每行的两个数代表了 w 和 v 
*/ 

int dp[1010];// dp[i] 存储容积为 i 的情况下的最大价值 
int main(){
	int t, m, w, v;
	cin >> t >> m;
	for (int i = 1; i <= m; i++){//m个物品 
		cin >> w >> v;//输入每个物品的体积和价值(时间、价值）
		for (int j = t; j >= w; j--){//从大到小枚举 
			dp[j] =  max(dp[j], dp[j-w] + v);
		}
	} 
	cout << dp[t];
	return 0;
}

同类型