主站
DreamJudge
院校信息
专业题库
模拟考试
机试真题
专业课程
答疑区
兑换中心
登录
注册
上岸
以下题解仅供学习参考使用。
抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在N诺是严格禁止的。
N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。
藕糖
2024年6月5日 18:05
采药 题解:
P1086
回复 0
|
赞 1
|
浏览 403
#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
|
赞 0
|
浏览 330
#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
|
赞 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
|
浏览 676
#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,...
wordC
2021年3月17日 20:57
1086-采药,动态规划,注释详细(c语言)
P1086
回复 0
|
赞 0
|
浏览 9.5k
推荐学习视频:背包问题 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; } ...
shmilyzsc
2021年2月28日 21:45
01背包问题 降维优化
P1086
回复 0
|
赞 0
|
浏览 8.6k
#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--...
James
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语言)