leeyupeng

leeyupeng@126.com

0%

poj.3624.Charm Bracelet(分支裁剪法)

发表于 更新于 分类于 ， 阅读次数： Valine：

0/1背包问题

题目

- 3624.Charm Bracelet

描述

有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值

剪枝

1.w==0
2.if ((ans - d)(v)[index].weight >= w (v)[index].desirability),使用粗略剪枝会超时，不靠谱
3.index w d 下一直往背包装，能够取得的最大值和当前的ans比较大小，小于当前ans 剪枝

回溯法DFS

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct charm
{
	int weight;
	int desirability;
};

vector<charm>* v = NULL;
int ans = 0;
void dfs(int index,int w,int d)
{
	if (index < 0)
	{
		ans = ans > d ? ans : d;
		return;
	}

	//剪枝
	if (w == 0)
	{
		ans = ans > d ? ans : d;
		return;
	}

	//剪枝
	//if ((ans - d)*(*v)[index].weight >= w * (*v)[index].desirability)
	//{
	//	return;
	//}

	//剪枝
	if(ans > d)
	{
		int anstemp = d;
		int wtemp = w;
		int indextemp = index;
		while (indextemp >= 0 && wtemp >= (*v)[indextemp].weight)
		{
			anstemp += (*v)[indextemp].desirability;
			wtemp -= (*v)[indextemp].weight;
			indextemp--;
		}
		if (indextemp >= 0)
		{
			anstemp += wtemp * (*v)[indextemp].desirability / (*v)[indextemp].weight;
		}
		if (ans >= anstemp)
		{
			return;
		}
	}

	if ((*v)[index].weight <= w)
	{
		dfs(index - 1, w - (*v)[index].weight, d + (*v)[index].desirability);
	}

	dfs(index - 1, w, d);
}
bool cmp(charm c1, charm c2)
{
	if (c1.desirability * c2.weight == c2.desirability * c1.weight)
	{
		return c1.weight < c2.weight;
	}
	else
	{
		return 1.0f * c1.desirability / c1.weight < 1.0f * c2.desirability / c2.weight;
	}
}
int CharmBracelet(vector<charm>* v, int n, int m)
{
	sort(v->begin(), v->end(), cmp);

	dfs(n-1,m,0);

	return ans;
}
int main()
{
	int n, m;
	cin >> n >> m;
	v = new vector<charm>(n);
	for (int i = 0; i < n; i++)
	{
		cin >> (*v)[i].weight;
		cin >> (*v)[i].desirability;
	}
	int result = CharmBracelet(v, n, m);
	delete v;
	v = NULL;
	cout << result << endl;
	return 0;
}