ptasknapsack算法.cpp

自己编写的

#include <iostream>
#include <algorithm>
const int N = 30;
using namespace std;

int table[10] = {0,1,3,7,15,31,63,127,255,511};
typedef struct goods 
{
	int value;   // 物品价值
	int weigh;   // 物品重量
}Goods;

bool comp(Goods& a,Goods& b)
{
	return (a.value * 1.0)/a.weigh > (b.value*1.0)/b.weigh; // 价值密度可能为浮点数
}

int main()
{
	int n;      // 物品总数
	int W;      // 背包总重量
	Goods bagGoods[N]; 
	int i,j,t;
	scanf("%d%d",&n,&W);
	for(i = 0; i < n; i++)
		scanf("%d",&bagGoods[i].value);
	for(j = 0; j < n; j++)
		scanf("%d",&bagGoods[j].weigh);
	sort(bagGoods,bagGoods+n,comp);           // 按价值密度排序
	int k = 3;
	int digital[N];                 // 穷举数组
	int cost = 0,Max = 0,num;
	int total = table[k],temp,b;
	for(i = 0; i <= total; i++){
		t = 0;
		temp = W;
		b = i;
		memset(digital,0,sizeof(digital));
		while(b && t < k){               // 穷举搜索部分
			digital[t++] = b % 2;
			b >>= 1;
		}
		num = 0;
		for(j = 0; j < k; j++){
			if(digital[j]){
				num += bagGoods[j].value * digital[j];
				if(bagGoods[j].weigh > temp)
					break;
				temp -= bagGoods[j].weigh;
			}

		}
		if(j == k)
			cost = num;
		for(j = k; j < n; j++){
			if(bagGoods[j].weigh <= temp){ // 这一步骤有待改进，有可能引起误差，
				                           // 最主要的是可以继续执行下去，只要背包
				                           // 依旧有剩余空间，但PTAS策略并未考虑此种
				                           // 情况，这正是造成误差的原因
				temp -= bagGoods[j].weigh;
				cost += bagGoods[j].value;
			}
			else
				break;
		}
		if(cost > Max)
			Max = cost;
	}
	printf("%d\n",Max);
	return 0;
}