【NC16650】采药

本文主要是介绍【NC16650】采药，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

采药

动态规划-01背包

思路

01背包例题，思路见同一专栏的【NC16693】装箱问题，这里只贴出代码。

代码

#include <stdio.h>int max(int a, int b) { return a > b ? a : b; }int main(void) {int n = 0, m = 0;scanf("%d%d", &n, &m);// a[m][2] 将耗时和价值合成了一个数组int a[m][2], dp[n + 1], i = 0, j = 0;for (i = 0; i < m; i++) {scanf("%d%d", &a[i][0], &a[i][1]);}for (i = 0; i <= n; i++) {dp[i] = 0;}for (i = 0; i < m; i++) {for (j = n; j >= a[i][0]; j--) {dp[j] = max(dp[j], dp[j - a[i][0]] + a[i][1]);}}printf("%d\n", dp[n]);return 0;
}

这篇关于【NC16650】采药的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---