P1086 采药 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年6月5日 18:05

采药题解：

P1086

回复 0 | 赞 1 | 浏览 419

#include <iostream> #include <vector> #include <algorithm> // 用于 std::max using namespace std; int main(void) { int T, M; while (cin >> T >> M) { vector<int> time(M), values(M); for (int i = 0; i < M; i++) { c...

2024年3月22日 16:28

采药题解：数组大小开的不好就会错OVO

P1086

回复 0 | 赞 0 | 浏览 349

#include <stdio.h> #include <stdlib.h> int t,m; int w[10000]; int v[10000]; int dp[1000][10000]; int max(int a,int b) { if(a>=b)return a; else return b; } int main() { while(scanf("%d%d",&t,&m)!=EOF) { //dp[i][j]采前i个草药，时间为j的最大价值 ...

2021年1月14日 11:08

01背包二维数组实现

P1086

回复 1 | 赞 3 | 浏览 9.1k

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; /* f[i][j] 表示只看前i个物品,总体积是j的情况下,总价值最大是多少 f[i][j]: 1 不选第i个物品 : f[i][j]=f[i-1][j] ; 2 选第i个物品 : f[i][j]=f[i-1][j-v[i]]+w[i] f[0][0]=0; */ int f[105][1005]; int w[105]; int v[105]; ...

2023年8月6日 10:53

采药题解：只需要O(n)的dp数组，0-1背包问题套路

P1086

回复 0 | 赞 1 | 浏览 690

#include<iostream> #include<cstring> using namespace std; int main(){ int dp[1001], w, v, T, M; cin >> T >> M; memset(dp, 0, sizeof(dp)); for(int i=1; i<=M; i++){ cin >> w >> v; for(int j=T; j>=w; j--) dp[j] = max(dp[j-w]+v, dp[j]);...

快乐小土狗

2022年10月21日 23:27

【P1086 采药】背包问题、动态规划

P1086

回复 0 | 赞 3 | 浏览 4.3k

思路首先，这是一道背包问题，其实就是动态规划。我们用fi,jfi,j表示可以采前面ii种药，用jj个时间单位能够采到药的最大价值。一道01背包问题,01背包，就是一种物品只能有取和不取两种，当我们来到fi,jfi,j时，可以采一次第ii药也就是fi,j−tifi,j−ti，就是要留出titi来采这个药(肯定要使j≥tij≥ti才可以采)，当然也可以不采，那么就是fi−1,jfi−1,j就是这个第ii种药不采，采前面i−1i−1中药的最大价值。所以转移公式就是 {fi,...

2021年3月17日 20:57

1086-采药，动态规划，注释详细（c语言）

P1086

回复 0 | 赞 0 | 浏览 9.6k

推荐学习视频：背包问题 https://www.bilibili.com/video/BV1K4411X766 本题实际上就是0-1背包问题。 #include <stdio.h> #include <stdlib.h> //定义药的数据结构 typedef struct drug { int time; //采药所需时间 int cost; //药的价值 }drug; //求两个数的较大值 int max(int a, int b) { return a>b?a:b; } ...

2021年2月28日 21:45

01背包问题降维优化

P1086

回复 0 | 赞 0 | 浏览 8.7k

#include <bits/stdc++.h> using namespace std; const int N = 1010; int f[N]; int w[N], v[N]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= m; i++) cin >> v[i] >> w[i]; for(int i = 1; i <= m; i++) for(int j = n; j >= v[i]; j--...

2021年1月14日 12:16

01背包一维数组

P1086

回复 0 | 赞 1 | 浏览 10.0k

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int f[105][1005]; int w[105]; int v[105]; int t,m; int main(){ cin>>t>>m; for(int i=1;i<=m;i++){ ...

题目采药

题解数量8

热门题解

1 01背包二维数组实现

2 【P1086 采药】背包问题、动态规划

3 采药题解：

4 01背包一维数组

5 采药题解：只需要O(n)的dp数组，0-1背包问题套路

6 01背包问题降维优化

7 采药题解：数组大小开的不好就会错OVO

8 1086-采药，动态规划，注释详细（c语言）