背包问题：c++回溯法求解背包问题

1.问题的重述：

      给定n种物品和一个背包。物品i的重量是wi，其价值为pi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

2.问题的分析

      根据题目所给的信息可知就是在wi<c时可以放入物品，并且结合要求价值最大这一点来进行挑选，例如：

共有5种物品，即n=5；背包容量c=30；各物品的重量 wi[5]={15,5,6,12,9};各物品的价值为： p[i]={25,16,14,13,36};

所以所求背包中的物品的价值最大就是 while(wi<=c) p=max.当wi>c,退出，并且输出最大的价值p.

3.思路

     由于所给的信息较多，所以考虑用类来进行封装，这样看起来比较有清晰而且有条理。

源代码如下：
 

// Knapsack-1.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

class Bag
{
private :
	int c;  //背包容量
	int n;   //物品数量
	int *w;   //各物品重量
	int *p;   //各物品价值
	int *x;   //解向量
	int cw;   //当前重量
	int cv;   //当前价值
	int bestv;    //当前最优价值
	int *bestx;   //当前最优价值对应的解
public:
	Bag();
	~Bag();
	void Output();
	void Set(int n);
	void Input();
	void Backtrack(int t);
};

Bag::Bag()
{
	n = 0;
	cw = cv = bestv = 0;
	w = p = x = bestx = NULL;
}

Bag::~Bag()
{
	delete x;
	delete p;
	delete w;
	delete bestx;
}

void Bag::Set(int n)
{
	this->n = n;
	x = new int[n];
	p = new int[n];
	w = new int[n];
	bestx = new int[n];
}

void Bag::Input()
{
	int i;
	cout << "请输入背包的容量：" << endl;
	cin >> c;
	cout << "请输入各物品重量:" << endl;
	for (i = 0; i < n; i++)
		cin >> w[i];
	cout << "请输入各物品价值：" << endl;
	for (i = 0; i < n; i++)
		cin >> p[i];
}

void Bag::Output()
{
	int i;
	cout<<"所选物品为（1代表已选择，0代表未选择）" << endl;
	for (i = 0; i<n; i++)
		cout << bestx[i] << "  ";
	cout << endl;
	cout << "背包所装的物品的最大价值为:"<<bestv << endl;
}

void Bag::Backtrack(int t)
{
	if (t > n - 1)
	{
		if (cv > bestv)
		{
			bestv = cv;
			for (int i = 0; i < n; i++)
				bestx[i] = x[i];
		}
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			x[t] = i;
			if (i == 0)
				Backtrack(t + 1);
			else
				if (cw + w[t] <= c)
				{
					cw = cw + w[t];
					cv = cv + p[t];
					Backtrack(t + 1);
					cw = cw - w[t];
					cv = cv - p[t];
				}
		}
	}
}

int main()
{
	Bag M;
	int n;
	cout << "请输入物品的数量:" << endl;
	cin >> n;
	M.Set(n);
	M.Input();
	M.Backtrack(0);
	M.Output();
    return 0;
}

最后的结果为：77

截图如下：

最后

以上就是风趣金毛为你收集整理的背包问题：c++回溯法求解背包问题的全部内容，希望文章能够帮你解决背包问题：c++回溯法求解背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。