如何做装修网站,专业营销的网站建设公司排名,上海心橙科技网站建设,上海建筑建材业信息网注意事项#xff1a; 本题是动态规划—01背包的扩展题#xff0c;dp和优化思路不多赘述。
题目#xff1a; 辰辰是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大的医师。 为此#xff0c;他想拜附近最有威望的医师为师。 医师为了判断他的资质 本题是动态规划—01背包的扩展题dp和优化思路不多赘述。
题目 辰辰是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。 为此他想拜附近最有威望的医师为师。 医师为了判断他的资质给他出了一个难题。 医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同的草药采每一株都需要一些时间每一株也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。” 如果你是辰辰你能完成这个任务吗
输入格式 输入文件的第一行有两个整数 T和 M用一个空格隔开T代表总共能够用来采药的时间M代表山洞里的草药的数目。 接下来的 M行每行包括两个在 1到 100之间包括 1和 100的整数分别表示采摘某株草药的时间和这株草药的价值。
输出格式 输出文件包括一行这一行只包含一个整数表示在规定的时间内可以采到的草药的最大总价值。
数据范围 1≤T≤1000, 1≤M≤100
输入:
70 3
71 100
69 1
1 2输出
3#include cmath
#include cstring
#include iostream
#include algorithm
using namespace std;const int N 1010;
int n, m;
int v[N], w[N];
int f[N];int main () {cin m n; //和01背包唯一不同的点先接受体积m再接收数量nfor (int i 1; in; i) cin v[i] w[i];//01背包模板for (int i 1; in; i) {for (int j m; jv[i]; j--) {f[j] max(f[j], f[j-v[i]] w[i]);}}cout f[m];
}思路 就是01背包的裸题没啥可讲思路去01背包那道里面看吧
声明 算法思路来源为y总详细请见https://www.acwing.com/ 本文仅用作学习记录和交流
