knap.h

动态规划算法求解0-1背包问题,动态规划算法knapsack求最优值

#include<iostream>

using namespace std;

class Knap

{
	friend int Knapsack(int p[],int w[],int c,int n );

public:
	void print();
private:
	int Bound(int i);
	void Backtrack(int i);

	int c;//背包容量
	int n; //物品数
	int *w;//物品重量数组
	int *p;//物品价值数组
	int cw;//当前重量
	int cp;//当前价值
	int bestp;//当前最优值
	int *bestx;//当前最优解
	int *x;//当前解
};

class Object
{
	friend int Knapsack(int p[],int w[],int c,int n);

public:
	int operator<=(Object a)const
	{
		return (d>=a.d);
	}

private:

	int ID;
	float d;

};

int Knapsack(int p[],int w[],int c,int n);