ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【模板】01背包问题 [打印本页]

---

作者: 立山    时间: 2023-5-27 08:49
标题: 【模板】01背包问题
一个在旅途中的长者有一个最多能用\(M\)公斤的背包，现在有\(n\)件物品，它们的重量分别是\(W1，W2，...,Wn\),它们的价值分别为\(C1,C2,...,Cn\).求旅行者能获得最大总价值。
输入

• 第1行：两个整数，\(M\)（背包容量，\(M\le200\)）和\(n\)（物品数量，\(n\le30\)）；
  
• 第\(2\)至\(n+1\)行：每行两个整数\(Wi\),\(Ci\)，表示每个物品的重量和价值。
  

输出

• 仅一行，一个数，表示最大总价值。
  

样例

样例输入1

1. 10 4
2. 2 1
3. 3 3
4. 4 5
5. 7 9

复制代码

样例输出1

1. 12

复制代码

解析

好了，这是一个经典的01背包问题
做01背包问题只要记住一个公式：
d[j]=max(d[j],d[j-w]+c)；
其中 d 数组表示当前容量可以装的最大价值，w 是重量，c 是价值。
在公式中，我们在装和不装中选一种：

• 不装：就是当前的最大重量 d[j]
  
• 装：先在当前容量 j 中给 当前重量 w 预留一个位置 （d[j-w]），然后在加上当前价值 c
  

最后，用max函数在它们当中选大的那个就可以了
公式中有 i 有 j ，那么这是一个双重循环。
Code

[code]#include                  using namespace std;int v,n,d[2000],c[50],w[50];     //d数组的下标表示容量int main(){        cin >> v >> n;      //v表示容量，n表示数量         for(int i=1;i>w >>c;        for(int i=1;i=w;j--)                        //01背包中，第二重循环要倒序，从v到w                {                        d[j]=max(d[j],d[j-w]+c);  //公式                 }        cout

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4