算法十七：背包问题1

比眉伴天荒 2022-05-21 07:55 160阅读 0赞

### **描述** ###

n种物品，每种物品有相应的价值和体积，同时物品还分为两类，一类是“单个物品”，即该种物品只有一个；一类是“多个物品”，即该种物品有无限个。

现在你有一个体积为V的背包，那么该装些什么物品到背包里使得价值之和最大呢？

### **输入** ###

第一行包含两个正整数n,V。

接下来n行，每行代表一种物品。每行的第一个数字表示该物品的种类（若为0表示“单个物品”，若为1表示“多个物品”），第二个数字表示该物品的价值，第三个数字表示该物品的体积。

### **输出** ###

输出一个整数，表示最大的价值之和。

### **输入** ###

5 8

0 6 8

0 7 3

1 1 1

0 8 1

0 5 2

### **输出** ###

### 22 ###

### **样例解释** ###

第三种物品有无限个，其余都是单个物品。

若我们放入物品1，则背包已经装满，此时价值和为6；

若我们放入物品2、4、5，背包所剩体积为8-3-1-2=2，此时价值和为7+8+5=20；

若我们放入8个物品3，背包装满，此时价值之和为8×1=8；

若我们放入物品2、4、5，再放两个物品3，则背包装满，此时价值和为7+8+5+2×1=22。

可以验证，最优答案就是22。

### **一. 伪代码** ###

![70][]

### **二. 具体实现（C++）** ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
const int N = 5005;  
//f:动态规划的数组，f\[i\]表示容量为i的背包的最大价值  
int f\[N\];  
// n：物品个数  
// V：背包的体积  
// t：长度为n的数组，第i个元素若为0，表示物品i为单个物品；若为1，表示物品i为多个物品。（i下标从0开始，下面同理）  
// w：长度为n的数组，第i个元素表示第i个物品的价值  
// v：长度为n的数组，第i个元素表示第i个物品的体积  
// 返回值：最大价值之和  
int getAnswer(int n, int V, vector<int> t, vector<int> w, vector<int> v) \{  
for(int i=0; i<n; ++i)  
if(t\[i\] == 0)  
for(int j=V; j>=v\[i\]; --j)  
f\[j\] = max(f\[j\],f\[j-v\[i\]\] + w\[i\]);  
else//完全背包，顺序枚举  
for(int j=v\[i\]; j<=V; ++j)  
f\[j\] = max(f\[j\],f\[j-v\[i\]\]+w\[i\]);  
return f\[V\];  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220521/45c062d492724509840d3a69b6890c30.png