首页
DreamJudge
院校信息
考研初试
机试真题
讨论区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
GENARDING
2025年3月16日 16:02
01背包问题,vector版
P1086
回复 0
|
赞 5
|
浏览 543
#include <bits/stdc++.h> using namespace std; int main() { int t,m; while(cin>>t>>m){ vector<pair<int,int>> v(m); for(int i=0;i<m;i++ ){ cin>>v[i].first>>v[i].second; } vector<int> dp(t+1,0); for(int i=0;i<...
zxjrheaven
2025年3月15日 19:42
采药 题解:暴力01,改了半天bug发现数组取反了(恼
P1086
回复 0
|
赞 1
|
浏览 429
#include <bits/stdc++.h> using namespace std; int dp[105][1005] = {0}; struct node { int time; int value; } obj[105]; void guihua(int m, int n) { for (int i = 1; i <= n; i++) { for (int j = 0; j <= m;...
RingoCrystal
2025年1月31日 10:02
采药 题解:经典01背包问题
P1086
回复 0
|
赞 15
|
浏览 826
#include <bits/stdc++.h> using namespace std; int main(){ int t,n; while(cin>>t>>n){ int dp[n+1][t+1]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; for(int j=0;j<=t;j++){...
Candour
2025年1月17日 17:00
采药(01背包) 题解:
P1086
回复 0
|
赞 3
|
浏览 605
#include<bits/stdc++.h> using namespace std; const int N = 1010; int t[N], w[N], dp[N]; int T, m; int main() { cin >> T >> m; for(int i = 1; i <= m; i ++) cin >> t[i] >> w[i]; for(int i = 1; i <= m; i ++) for(int j = T; j >= t[i];...
藕糖
2024年6月5日 18:05
采药 题解:
P1086
回复 0
|
赞 2
|
浏览 757
#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...
xjnotywlq
2024年3月22日 16:28
采药 题解:数组大小开的不好就会错OVO
P1086
回复 0
|
赞 4
|
浏览 841
#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的最大价值 ...
James
2021年1月14日 11:08
01背包二维数组实现
P1086
回复 1
|
赞 7
|
浏览 9.7k
#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
|
赞 4
|
浏览 983
#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
|
赞 8
|
浏览 4.9k
思路 首先,这是一道背包问题,其实就是动态规划。 我们用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,...
wordC
2021年3月17日 20:57
1086-采药,动态规划,注释详细(c语言)
P1086
回复 0
|
赞 1
|
浏览 10.7k
推荐学习视频:背包问题 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; } ...
1
2
题目
采药
题解数量
12
发布题解
在线答疑
热门题解
1
采药 题解:经典01背包问题
2
【P1086 采药】背包问题、动态规划
3
01背包二维数组实现
4
01背包问题,vector版
5
采药 题解:数组大小开的不好就会错OVO
6
采药 题解:只需要O(n)的dp数组,0-1背包问题套路
7
采药(01背包) 题解:
8
采药 题解:
9
01背包一维数组
10
1086-采药,动态规划,注释详细(c语言)