415-回溯算法解决0-1背包问题

迈不过友情╰ 2022-09-05 00:29 175阅读 0赞

## 0-1背包问题 ##

有一组物品，其重量分别是:w1,w2,…wn，其价值分别是v1,v2,…,vn，现在有一个背包，其容量是C，  
**问怎么把物品装入背包，能够使背包的价值最大化？**

**所以说，0-1背包问题就是要么装入物品，要么不装入物品，不存在装入物品的一部分。**

最后装入背包的那些物品不就是原始物品的一个子集吗！！！  
**我们可以用子集树解决！！！**

**我们用物品的重量来代表物品**

int w[] = {
         12,5,8,9,6 };//物品的重量
    int v[] = {
         9,2,4,7,8 };//物品的价值
    const int length = sizeof(w) / sizeof(w[0]);//物品的个数
    vector<int> x;//存储已经选择的物品
    vector<int> bestx;//记录最优选择的物品
    int c = 20;//背包的容量
    int cw = 0;//已选择物品的重量
    int cv = 0;//已选择物品的价值
    int bestv = 0;//记录装入背包的物品的最大价值
    int r = 0;//记录未处理的物品的总价值
    
    void func(int i)
    {
        
    	if (i == length)
    	{
        
    		if (bestv < cv)//如果题目是最优价值有很多情况，就判断==
    		{
        
    			bestv = cv;
    			bestx = x;
    		}
    	}
    	else
    	{
        
    		r -= v[i];//扣除处理过的物品的价值
    		if (cw + w[i] <= c)//剪枝，已选择物品的重量 + 即将选择的第i号物品的重量
    		{
        
    			cw += w[i];
    			cv += v[i];
    			x.push_back(w[i]);//装的是物品的重量，代表物品
    			func(i + 1);
    			cw -= w[i];
    			cv -= v[i];
    			x.pop_back();//回溯上去
    		}
    
    		//剪枝，bestv   cv + [i+1,i+2.....n]总价值 > bestv
    		//当前选择的物品的价值+剩余可选物品的价值的和>当前的最大价值
    		if (cv + r > bestv)
    		{
        
    			func(i + 1);
    		}
    		r += v[i];//回溯到父节点
    	}
    }
    int main()
    {
        
    	for (int val : v)
    	{
        
    		r += val;
    	}
    	func(0);
    	for (int w : bestx)
    	{
        
    		cout << w << " ";
    	}
    	cout << endl;
    	cout << "bestv:" << bestv << endl;
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/08a0784e5a634ce4a74b842bdeb328c8.png