0-1问题.cpp

湖南大学ACM-OJ的部分题目代码

#include<iostream>
using namespace std;
int main()
{
	int n,c;
	int *w,*v,*head,*x;
	int p[21][2];
	cin>>n;
	cin>>c;
    w=new int[n+1];
	v=new int[n+1];
	x=new int[n+1];
	head=new int[n+2];
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	
    int left=0,right=0,next=1;
	head[n+1]=0;
	p[0][0]=0;p[0][1]=0;  //初始值为 0 weight，0 value
	head[n]=1;            //第一个在p数组的下标
	for( i=n;i>=1;i--)
	{
		int k=left;       //从前一个集合的第一个开始
		for(int j=left;j<=right;j++)
		{
			if(p[j][0]+w[i]>c)   //当重量超过时退出循环
				break;
		int y=p[j][0]+w[i],m=p[j][1]+v[i];//前一个集合每个元素加上此物品后的重量和价值
			while(k<=right && p[k][0]<y)  //将重量小于y的项拷贝到新的集合
			{
				p[next][0]=p[k][0];
				p[next++][1]=p[k++][1];
		
			}
           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;
			}
			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];
		}
		left=right+1;                             //移到下个集合
		right=next-1;
		head[i-1]=next;
	}
	int j=p[head[0]-1][0],m=p[head[0]-1][1];
	    for(i=0;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];
					cout<<i<<" ";
					break;
				}
		}
        cout<<p[next-1][1]<<endl;
		return 0;
}