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

122 阅读 0 评论 81 点赞

我是靠谱客的博主风趣金毛，这篇文章主要介绍背包问题：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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 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;
}