P1616 疯狂的采药(完全背包模板)

本文主要是介绍P1616 疯狂的采药(完全背包模板)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//这是一道完全背包的题，并且需要用一维数组优化空间，否则会MLE 
#include <bits/stdc++.h>
using namespace std;
//t表示可以用来采药的时间（相当于背包容量）
//m表示草药的数目（相当于物品数量）
int t, m;  //m<=10^4,t<=10^7 
//w[i]表示采摘第i种草药需要花费的时间（相当于背包模型中物品的体积） 
//v[i]表示第i种草药的价值（相当于背包模型中物品的价值） 
int w[10001], v[10001]; //w[j]<=10^4, v[j]<=10^4 
//dp[j]表示在j时间内，可以采摘到的最大价值，那么dp[t]就是我们想要的答案 
long long dp[10000001]; //int会爆掉，特例：t=10^7,m=1,w[1]=1,v[1]=10^4,dp[1]=10^11 
int main()
{ //t表示可以用来采药的时间，m表示草药的数目 cin >> t >> m;for(int i=1; i<=m; ++i){cin >> w[i] >> v[i];} //遍历草药 for(int i=1; i<=m; ++i){//每种草药可以重复采摘，所以顺序 for(int j=w[i]; j<=t; ++j){//采摘第i种草药和不采摘第i种草药种选一个最大的 dp[j]=max(dp[j], dp[j-w[i]]+v[i]);} }cout << dp[t];return 0;
}

 

这篇关于P1616 疯狂的采药(完全背包模板)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---