用动态规划算法解01背包问题时，其中要使用数组p[][2]来记录，我想问一个问题，
那就是如何预先确定p的第一维的大小？请各位高手替我解答一下。
(程序可以参见《算法设计与分析》(王晓东 编著)动态规划一章p96-p98)
#include<iostream>
#include<fstream>
#include<cstdio>
using namespace std;
typedef float T;
//template<class T>
void Traceback(int n,T w[],T v[],T p[][2],int *head,int x[])
{
	T j=p[head[0]-1][0],
		m=p[head[0]-1][1];
	for(int i=1;i<=n;i++)
	{
		x[i]=0;
		for(int k=head[i+1];k<=head[i]-1;k++)
		{
			if(p[k][0]+w[i]==j && p[k][1]+v[i]==m)
			{
				x[i]=1;
				j=p[k][0];
				m=p[k][1];
				break;
			}
		}
	}
}

//template<class T>
T Knapsack(int n,int c,T v[],T w[],T p[][2],int x[])
{
	int *head=new int[n+2];
	head[n+1]=0;
	p[0][0]=0;
	p[0][1]=0;
	int left=0,right=0,next=1;
	head[n]=1;

	for(int i=n;i>=1;i--)
	{
		int k=left;
		for(int j=left;j<=right;j++)
		{
			if(p[j][0]+w[i]>c) break;
			T y=p[j][0]+w[i],
				m=p[j][1]+v[i];
			while(k<=right && p[k][0]<y)
			{
				p[next][0]=p[k][0];
				p[next][1]=p[k][1];
				next++;
				k++;
			}
			if(k<=right && p[k][0]==y)
			{
				if(m<p[k][1]) m=p[k][1];
				k++;
			}
			if(m>p[next-1][1])
			{
				p[next][0]=y;
				p[next][1]=m;
				next++;
			}
			while(k<=right && p[k][1]<=p[next-1][1])
			{
				k++;
			}
		}
		while(k<=right)
		{
			p[next][0]=p[k][0];
			p[next][1]=p[k][1];
			next++;k++;
		}
		left=right+1;
		right=next-1;
		head[i-1]=next;
		//cout<<next<<" ";
	} 
	Traceback(n,w,v,p,head,x);
	return p[next-1][1];
}

int main()
{
	int i,n,c;
	T maxV;
	T *v;
	T *w;
	int *x;
	float p[65536][2];//如何预先确定p的大小？
	ifstream fcin("01packetDataIn.txt");
	fcin>>n>>c;
	cout<<n+c+n*c<<endl;
	v=new T[n+1];
	w=new T[n+1];
	x=new int[n+1];
	//p=new float[c+2][2]
	for(i=1;i<=n;i++) fcin>>v[i];
	for(i=1;i<=n;i++) fcin>>w[i];
         maxV=Knapsack(n,c,v,w,p,x);
	cout<<"Max value is : "<<maxV<<endl;
	for(i=1;i<=n;i++) cout<<x[i]<<" ";
	cout<<endl;
	delete[] v;
	delete[] w;
	delete[] x;
	return 0;
}

• pku的老大大们，帮个忙吧！ (0) ACM30413 2005-12-23 21:02:13
  • 找标程 (0) ACM30434 2005-12-23 21:04:22
    • Re:找标程 (0) ACM30413 2005-12-23 21:27:23
    • Re:哪儿？！ (0) ACM30413 2005-12-23 21:27:57