背包问题（分支限界法）_给定背包价值/重量系数为{9/7,5/4,3/3,1/2},背包限定总重不能超过10,使用分支限界

题目

使用分支限界法求解0-1背包问题。 给定n(n<=10)种物品和一个容量为c的背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=100)。 在装入背包的物品时，对每种物品只有两个选择：装入或不装入。 如何选择装入背包中的物品，使得装入背包中物品的总价值最大?

输入格式:
第1行，输入物品个数n和背包容量c 第2行-n+1行，每个物品的重量和价值

输出格式:
背包能获得的最大价值

输入样例:
在这里给出一组输入。例如：

5 10
2 6
2 3
6 5
5 4
4 6
1
2
3
4
5
6

输出样例:
在这里给出相应的输出。例如：

15
1

答案

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int v,w;
	double sim;
};
bool cmp(Node x,Node y){
	return x.sim>y.sim;
}
int main()
{
	int n,W;
	cin>>n>>W;
	Node node[n];
	for(int i=0;i<n;i++)
	{
		cin>>node[i].w>>node[i].v;
		node[i].sim=1.0*node[i].v/node[i].w;
	}
	sort(node,node+n,cmp);
//	cout<<"----------------------------------"<<endl;
//	for(int i=0;i<n;i++)
//	cout<<node[i].w<<" "<<node[i].v<<endl;
	int high=W*node[0].sim,low=0,tmp=W;
	for(int i=0;i<n;i++)
	{
		if(tmp>=node[i].w) 
		{
			low+=node[i].v;
			tmp-=node[i].w;
		}
	}
//	cout<<high<<low<<endl;
	int sum_w=0,sum_v=0,index;
	int a[n+1][2],ans[n];
	for(int i=1;i<n+1;i++)
	{
		for(int j=0;j<2;j++)
		{
			if(sum_w+node[i-1].w*j>=W) a[i][j]=0;
			else a[i][j]=(W-sum_w-j*node[i-1].w)*node[i].sim+sum_v+j*node[i-1].v;
			if(a[i][j]<low||a[i][j]>high) a[i][j]=0;
//			cout<<a[i][j]<<" ";
		}
		if(a[i][0]==a[i][1]&&a[i][0]!=0) index=1;
		else index=max_element(a[i],a[i]+2)-a[i];
//		cout<<endl<<index<<endl;
		ans[i-1]=index;
		sum_w+=index*node[i-1].w;
		sum_v+=index*node[i-1].v;
	}
	cout<<sum_v;
} 
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

注意

如果每行的两个数相等，即是否放入上一个物品预期价值都是一样的，那么分两种情况考虑：

1. 如果二者相等且不为0，因为越靠前的单价越高，我们就选择将上一个物品放入（即单价优先）
2. 如果二者相等但都为0，那么我们就不选以保持当前的总重量最小，为后续操作提供更大的容量