0/1背包问题（蛮力法）

朴灿烈づ我的快乐病毒、 2022-04-16 05:05 299阅读 0赞

### **问题描述：** ###

给定n个重量为\{w1,w2,w3,....,wn\}、价值为\{v1,v2,v3,...,vn\}的物品和一个容量为C的背包，0/1背包问题是求解这些物品中的一个最有价值的子集，并且要能够装到背包中。

### 蛮力法： ###

**算法描述：**

使用蛮力法解决0/1背包问题，就是将所有的物品装入背包的可能全部列举出来（背包问题的蛮力解法是穷举这些物品的所有子集，找出能够装到背包中的所有子集，并在这些子集中找出价值最大的子集）。这个可以通过递归的方式实现。递归的过程可以看成是对一棵树的深度优先遍历：

![2018032513522875][]

例如上图，假设从背包中的1号物品开始列举所有的可能。如果每一层仅仅简单的在循环中使用递归，则该程序就不会结束。需要使用一个一维向量用于标记当前哪些编号已经装入了。例如，当前1号物品已经装入背包，首先标记1号物品已经装入。之后，在循环中首先选择2号物品，如果没有超出背包的最大承重的话，标记2号物品已经装入。当前还有3、4号物品没有装入，所以继续递归尝试装入3、4号物品。在装入2号物品之后的所有可能的递归全部完成后，修改当前标记，并将2号物品从背包中拿出，之后就可以递归遍历放入3号物品之后的可能的情况了。  
代码如下：

#include <iostream>
    
    #include <vector>
    #define PAC_MAX_VOL	10	//背包最大承重10
    using namespace std;
    
    void dfs(const vector<int> weights, const vector<int> vals, bool visit[], 
    int currWeight, vector<int> seq);
    
    void outputResult(vector<int> weights, vector<int> vals, bool visit[], 
    int currWeight, vector<int> seq);
    
    /**
    
    *	使用递归的方式遍历所有的可能
    
    */
    
    void dfs(const vector<int> weights, const vector<int> vals, bool visit[], int currWeight, vector<int> seq) 
    {
    
    	for (int i = 0; i < 4; ++i)
     {
    
    		if (!visit[i]) {
    
    			if (currWeight + weights[i] > PAC_MAX_VOL)
    
    				continue;
    
    			visit[i] = true;
    
    			seq.push_back(i);
                           //将当前步加入到序列中
    
    			dfs(weights, vals, visit, (currWeight + weights[i]), seq);	
    
    	               //基于当前状态深度遍历
    			seq.erase(find(seq.begin(), seq.end(), i));		
                            //从序列中删除
    
    			visit[i] = false;
    		}
    	}
    	outputResult(weights, vals, visit, currWeight, seq);
    
    	return;
    }
    /**
    
    *	输出当前结果
    
    */
    
    void outputResult(vector<int> weights, vector<int> vals, bool visit[], int currWeight,vector<int> seq) {
    
    	cout << "当前背包的重量是：" << currWeight << ", ";
    
    	int sumVal = 0;
    
    	for (int i = 0; i < 4; ++i)
    
    		if (visit[i])
    
    			sumVal += vals[i];
    
    	cout << "当前背包的总价值为：" << sumVal << endl;
    
    	cout << "当前结果集(编号)是：";
    
    	for (auto ele : seq) {
    
    		cout << ele << "  ";
    	}
    	cout << "\n-----------------------------" << endl;	
    }
    int main()
    {
    
    	const vector<int> weights = { 7,3,4,5 };		//各个物品的重量
    
    	const vector<int> vals = { 42,12,40,25 };		//各个物品的价值
    
    	vector<int> seq;
    
    	bool visit[4] = {false};			
            //用于在递归中表示当前已有哪些物品放在背包中了
    
    	dfs(weights, vals, visit, 0, seq);
    
        return 0;
    
    }

算法分析：

[2018032513522875]: /images/20220416/eb0377e91714483eb56e654d030629de.png