贪心算法实现0-1背包问题，包含k阶优化

在用贪心算法实现0-1背包问题的基础上，加以改进，实现了k阶优化，值得下载，哈哈！

#include “stdafx.h“
#include “iostream.h“
#include “iomanip.h“


//定义递归函数
void digui（int YouHua[]int nint kint XiaBiao[]int mint Ndouble cdouble w[]double p[]int BianHao[]int JiLu[]）   
//YouHua代表n个物品选择与未选择，1代表选择，0代表未选择；
//k代表阶数，或理解为取k个固定物品；
//XiaBiao代表取出第n个物品在YouHua中的下标；m=k;N=n物品个数；
//c代表总容量；w[]为物品各自重量;BianHao为物品编号从1到n;JiLu用来存储输出哪个物品；
{
	double Wsum=0;
	double Psum=0;
	double C;     //剩余容量
	C=c;
	
	
	//枚举所有可能解
	for（int i=n;i>0;i--）
	{
		int I=i-1;
		XiaBiao[k-1]=i-1;   //计算下标
		if（k>1）
			digui（YouHuai-1k-1XiaBiaomNcwpBianHaoJiLu）;
		else
		{
			for（int j=m-1;j>=0;j--）
				YouHua[XiaBiao[j]]=1;     //选中物品变为1
			for（int i=0;i			{
				if（YouHua[i]==1）
				{
					Wsum+=w[i];             
					Psum+=p[i];
				}
			}
			C=c-Wsum;                    //计算剩余容量
			
			//智能挑选
			for（int ii=I-1;ii>=0;ii--）   
			{ 
				if（YouHua[ii]==0&&w[ii]<=C）
				{
					C=C-w[ii];
					Psum=Psum+p[ii];
					YouHua[ii]=1;
				
					for（int jj=0;jj					{
						if（YouHua[jj]==1）
							JiLu[（BianHao[jj]-1）]=1;
						else
							JiLu[（BianHao[jj]-1）]=0;
					}
					if（C>=0）
					{
						for（int i1=0;i1							cout<						cout<<“剩余容量是：“<						cout<					}
					C=C+w[ii];
					Psum=Psum-p[ii];
					YouHua[ii]=0;
				}
			}
			
			for（int jj=0;jj			{
				if（YouHua[jj]==1）
					JiLu[（BianHao[jj]-1）]=1;
				else
					JiLu[（BianHao[jj]-1）]=0;
			}
			if（C>=0）
			{
				for（int i1=0;i1					cout<				cout<<“剩余容量是：“<				cout<				Psum=0;
				Wsum=0;
			}
		}
		
		
		//for（int h=0;h		//	cout<		
		
		//for（int ii=0;ii		//		cout<		//	cout<		for（int i1=0;i1			YouHua[i1]=0;
	}
}


	
void beibao（int YouHua[]double w[]double p[]double cint nint BianHao[]int XiaBiao[]）
{
	int k;
	int N;
	int m;
	double Wsum=0;
	double Psum=0;
	cout<<“请输入k阶优化值:“;
		cin>>k;
	N=n;
	m=k;

    //**************************************************
		//将k分为>n
		if（k>n&&k<0）
			cout<<“k值输入错误“<	//**************************************************
		if（k==n）
		{
			
			for（int i=0;i			{
				Wsum=Wsum+w[i];
			}
			if（Wsum>c）
				cout<<“输入k值错误本例中k不能等于“<			else
			{
				double Psum=0;
				for（int i=0;i				{
					Psum=Psum+p[i];
					YouHua[i]=1;
				}
				cout<<“最优价值为“<				cout<<“最优解为:“;
				for（int j=0;j				{
					if（YouHua[j]==1）
						BianHao[j]=YouHua[j];
					else
						BianHao[j]=0;
				}
				cout<				cout<<“即“<			}
		}
	//**************************************************


		if（k0）
		{
			int *YouHua;
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     233555  2010-12-14 21:57  huoxiang\Debug\huoxiang.exe

     文件     286384  2010-12-14 21:57  huoxiang\Debug\huoxiang.ilk

     文件      16413  2010-12-14 21:57  huoxiang\Debug\huoxiang.obj

     文件     203728  2010-12-08 14:17  huoxiang\Debug\huoxiang.pch

     文件     582656  2010-12-14 21:57  huoxiang\Debug\huoxiang.pdb

     文件       1784  2010-12-08 14:17  huoxiang\Debug\StdAfx.obj

     文件     107520  2010-12-15 10:15  huoxiang\Debug\vc60.idb

     文件     118784  2010-12-14 21:57  huoxiang\Debug\vc60.pdb

     文件       5127  2010-12-14 21:57  huoxiang\huoxiang.cpp

     文件       4560  2010-12-08 14:17  huoxiang\huoxiang.dsp

     文件        539  2010-12-08 14:17  huoxiang\huoxiang.dsw

     文件      58368  2010-12-15 10:16  huoxiang\huoxiang.ncb

     文件      53760  2010-12-15 10:16  huoxiang\huoxiang.opt

     文件       1334  2010-12-14 21:57  huoxiang\huoxiang.plg

     文件       1220  2010-12-08 14:17  huoxiang\ReadMe.txt

     文件        295  2010-12-08 14:17  huoxiang\StdAfx.cpp

     文件        769  2010-12-08 14:17  huoxiang\StdAfx.h

     目录          0  2010-12-15 15:52  huoxiang\Debug

     目录          0  2010-12-15 15:52  huoxiang

----------- ---------  ---------- -----  ----

              1676796                    19