C++数据结构--背包问题

柔光的暖阳◎ 2021-11-04 10:10 310阅读 0赞

**1.背包问题是最优化问题的一个具体例子  
问题可以描述为：  
给定一组物品，每种物品都有自己的大小和价格，在限定的总大小内，我们如何选择，才能使得物品的总价格最高。  
背包问题有几个版本，这里只研究0/1版本，即需要作出决策来选择(1)或抛弃（0）集合中的一个物品。  
  
  
Example：给出5个物品，背包容量为12  
![20130811092934921][]  
  
问题求解过程图解  
矩阵列下标索引代表背包大小，矩阵每个横坐标对应着一个物品,值代表背包加入物品后的值，**

**当背包大小足够时，并且加入的新物品能比背包存储相同容量的原有物品的值大，就加入物品**

**具体计算方法为：当matrix\[i-1\]\[cap-item.size\]+item.value大于matrix\[i-1\]\[cap\]时，就加入物品**

**矩阵每一行都记录着每加入一个物品每个容量对应的最优解**

**背包问题的最优解为矩阵最后一行最后一个元素**

**step1:加入物品1  
![20130811093121328][]  
step2-step3:加入物品2,3  
![20130811093149875][]  
....  
  
  
  
  
  
  
  
  
  
  
实现代码：  
\#include<iostream>  
\#include<iomanip>  
\#include<vector>  
using namespace std;  
  
  
class item  
\{  
public:  
int size; //物品大小   
int val;  //物品价值   
item(int s=0,int v=0):size(s),val(v)\{\}  
  
\};  
  
  
class knapsack  
\{   
private:  
vector<item> itemList; //物品列表   
int capacity;  //背包总大小   
 vector<vector<int>> matrix; //存储自底向上计算过程的解   
 void buildMaxValMatrix(); //实现背包问题的解   
  
 public:  
knapsack(vector<item> &v,int cpt):itemList(v),capacity(cpt),matrix(v.size()+1,vector<int> (cpt+1,0))  
\{   
buildMaxValMatrix();  
\}  
void showMatrix(); //输出矩阵   
void showKnapsack(); //输出被选入的背包信息   
  
\};  
  
  
void knapsack::buildMaxValMatrix()  
\{   
int numItem=itemList.size(); //物品总数   
int tempMax=0;   
int remainder=0;  
for(int i=1;i<=numItem;i++) //遍历物品   
\{   
for(int cpcity=1;cpcity<=capacity;cpcity++) //遍历背包大小   
\{   
matrix\[i\]\[cpcity\]=matrix\[i-1\]\[cpcity\]; //保持默认的最大值   
remainder=cpcity-itemList\[i-1\].size; //加入新物品后背包剩余大小   
if(remainder>=0)  
\{   
tempMax=matrix\[i-1\]\[remainder\]+itemList\[i-1\].val;  
  
if(tempMax>matrix\[i-1\]\[cpcity\]) //更新最大值   
 matrix\[i\]\[cpcity\]=tempMax;  
\}  
\}  
\}  
\}  
  
  
  
  
void knapsack::showMatrix()  
\{   
for(vector<int> v:matrix)  
\{   
for(int x:v)  
 cout<<setw(3)<<x<<ends;  
 cout<<endl;  
\}   
\}  
  
  
void knapsack::showKnapsack()  
\{   
int i=itemList.size();  
int cpcity=capacity;  
cout<<"optimal solution is: "<<matrix\[i\]\[capacity\]<<endl;  
cout<<"contain knapsacks: "<<endl;  
for(;i>0;i--)  //从矩阵最后一行往前遍历  
\{   
if(matrix\[i\]\[cpcity\]!=matrix\[i-1\]\[cpcity\]) //该行不等于前一行的最优解，说明有新物品加入背包  
 \{   
cout<<"knapsack : "<<i<<ends  //输出物品信息  
 <<"size : "<<itemList\[i-1\].size<<ends  
 <<"value: "<<itemList\[i-1\].val<<endl;  
 cpcity-=itemList\[i-1\].size; // 背包剩余大小  
 \}   
\}  
  
cout<<"remainding capacity : "<<cpcity<<endl; //未被利用的背包大小  
\}  
  
  
 int main ()   
\{   
 vector<item> v\{item(2,1),item(3,4),item(4,3),item(5,6),item(6,8)\};  
 knapsack kps(v,12);  
 kps.showMatrix();  
 cout<<endl;  
 kps.showKnapsack();  
  
  
 return 0;  
\}  
  
  
  
  
运行结果：  
![Center][]**

[20130811092934921]: /images/20211104/fa4d63baa3ca4cdd96d60e8c94cc21da.png
[20130811093121328]: /images/20211104/3fd1ec9691f74c6a8b3bcf0796f66bb7.png
[20130811093149875]: /images/20211104/a36e1e2ffc8d48f08d8c6123a1f8808f.png
[Center]: /images/20211104/bd56f0a9453c4543887f4077a0316034.png