【动态规划】0-1背包与完全背包之“采药“与“疯狂的采药“

你的名字 2022-09-05 04:10 98阅读 0赞

# 基础背包问题（0-1、完全）请见：[背包问题教程][Link 1] #

# P1048 \[NOIP2005 普及组\] 采药 [https://www.luogu.com.cn/problem/P1048][https_www.luogu.com.cn_problem_P1048] 0-1背包 #

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采**每一株**都需要一些时间，**每一株**也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

--------------------

一看就是0-1背包问题

#include <iostream>
    using namespace std;
    const int maxn = 1e4 + 5;
    const int maxW = 1e7 + 5;
    int n, W, w[maxn], v[maxn];
    long long f[maxW];
    int main() { 
      cin >> W >> n;
      for (int i = 1; i <= n; i++)
      	cin >> w[i] >> v[i];
      // C++ Version
    	for (int i = 1; i <= n; i++)
    	  for (int l = W; l >= w[i]; l--) 
    	  	f[l] = max(f[l], f[l - w[i]] + v[i]);
      cout << f[W];
      return 0;
    }

# P1616 疯狂的采药 [https://www.luogu.com.cn/problem/P1616][https_www.luogu.com.cn_problem_P1616] 完全背包 #

LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采**每一种**都需要一些时间，**每一种**也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是 LiYuxiang，你能完成这个任务吗？

此题和原题的不同点：

1.  **每种草药可以无限制地疯狂采摘。**
2.  **药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！**

--------------------

#include <iostream>
    using namespace std;
    const int maxn = 1e4 + 5;
    const int maxW = 1e7 + 5;
    int n, W, w[maxn], v[maxn];
    long long f[maxW];
    int main() { 
      std::cin >> W >> n;
      for (int i = 1; i <= n; i++) 
      	cin >> w[i] >> v[i];
      for (int i = 1; i <= n; i++)
        for (int l = w[i]; l <= W; l++)
          if (f[l - w[i]] + v[i] > f[l]) 
          	f[l] = f[l - w[i]] + v[i];
      cout << f[W];
      return 0;
    }

[Link 1]: https://thomas.blog.csdn.net/article/details/118884088
[https_www.luogu.com.cn_problem_P1048]: https://www.luogu.com.cn/problem/P1048
[https_www.luogu.com.cn_problem_P1616]: https://www.luogu.com.cn/problem/P1616