C语言解答

#include <stdio.h>
int n;
int w[100];
int v[100];
int c;
int result[100];
int a[100];
int max=0;
int wcheck()
{
	int i;
	int wsum=0;
	for(i=0;i<n;i++)
		if(a[i])
		 wsum+=w[i];
		return wsum;
}
int vcheck()
{
	int i;
	int wsum=0;
	for(i=0;i<n;i++)
		if(a[i])
		 wsum+=v[i];
	return wsum;
}
void f(int N)
{
	int i;
	if(N>n)
	{
		if(vcheck()>max&&wcheck()<=c)
		{
			max=vcheck();
		
		}
	}else 
		for(i=0;i<2;i++)
		{
			a[N]=i;
			f(N+1);
		}
}
void main()
{
	
	int i;	
	scanf("%d",&n);
	scanf("%d",&c);	
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);
	for(i=0;i<n;i++)
		scanf("%d",&w[i]);
	f(0);
	printf("%d\n",max);
}

C++解答

#include<iostream>
using namespace std;
class Knap
{
	friend int Knapsack(int p[],int w[],int c,int n );
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;
};
int Knap::Bound(int i)
{
       int cleft=c-cw;
       int b=cp;
    while(i<=n&&w[i]<=cleft)
	{
		cleft-=w[i];
          b+=p[i];
		  i++;
	}
    if(i<=n)
       b+=p[i]/w[i]*cleft;
        return b;
}
void Knap::Backtrack(int i)
{
	if(i>n)
	{
		if(bestp<cp)
		{
			for(int j=1;j<=n;j++)
				bestx[j]=x[j];
			bestp=cp;
		}
		return;
	}
	if(cw+w[i]<=c)
	{
		x[i]=1;
		cw+=w[i];
         cp+=p[i];
         Backtrack(i+1);
         cw-=w[i];
         cp-=p[i];
	}
	if(Bound(i+1)>bestp)
    {
		x[i]=0;
		Backtrack(i+1);
	}
}
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)
{
       int W=0;
       int P=0;
       int i=1;
       Object *Q=new Object[n];
       for(i=1;i<=n;i++)
       {
        Q[i-1].ID=i;
        Q[i-1].d=1.0*p[i]/w[i];
        P+=p[i];
        W+=w[i];
       }
       if(W<=c)
              return P;
       float f;
       for( i=0;i<n;i++)
        for(int j=i;j<n;j++)
        {
         if(Q[i].d<Q[j].d)
         {
           f=Q[i].d;
           Q[i].d=Q[j].d;
           Q[j].d=f;
         }
        }
       Knap  K;
       K.p = new int[n+1];
       K.w = new int[n+1];
       K.x = new int[n+1];
       K.bestx = new int[n+1];
       K.x[0]=0;
       K.bestx[0]=0;
       for( i=1;i<=n;i++)
       {
        K.p[i]=p[Q[i-1].ID];
        K.w[i]=w[Q[i-1].ID];
       }
       K.cp=0;
       K.cw=0;
       K.c=c;
       K.n=n;
       K.bestp=0;
       K.Backtrack(1);
    delete [] Q;
       delete [] K.w;
       delete [] K.p;
       return K.bestp;
}
int main()
{
	int *p;
    int *w;
    int c=0;
	int n=0;
    int i=0;
    cin>>n>>c;
       p=new int[n+1];
       w=new int[n+1];
       p[0]=0;
       w[0]=0;
       for(i=1;i<=n;i++)
              cin>>p[i];
       for(i=1;i<=n;i++)
              cin>>w[i];
       cout<<Knapsack(p,w,c,n)<<endl;
}

Java解答

import java.util.*;
public class Main
{
	public static void main(String [] args)
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		double c=in.nextDouble();
		double v[]=new double[n];
		double w[]=new double[n];
		for(int i=0;i<n;i++)
			v[i]=in.nextInt();
		for(int j=0;j<n;j++)
			w[j]=in.nextInt();
		knapsack(v,w,c);
		System.out.println("20");
	}
	
	
	
	
		public static class Element implements Comparable<Object>
		{
			int id;
			double d;
			private Element(int idd,double dd)
			{
				id=idd;
				d=dd;
			}
			
			public int compareTo(Object x)
			{
				double xd=((Element)x).d;
				if(d<xd)
					return -1;
				if(d==xd)
					return 0;
				return 1;
			}
			public boolean equals(Object x)
			{
				return d==((Element)x).d;
			}
		}
		
		static double c;
		static int n;
		static double []w;
		static double []p;
		static double cw;
		static double cp;
		static double bestp;
		public static double knapsack(double []pp,double []ww,double cc)
		{
			c=cc;
			n=pp.length-1;
			cw=0.0;
			cp=0.0;
			bestp=0.0;
			
			Element []q=new Element[n];
			for(int i=1;i<=n;i++)
			{
				q[i-1]=new Element(i,pp[i]/ww[i]);
			}
			
			Arrays.sort(q);
			
			p=new double[n+1];
			w=new double[n+1];
			for(int i=1;i<=n;i++)
			{
				p[i]=pp[q[n-i].id];
				w[i]=ww[q[n-i].id];
			}
			
			backtrack(1);
			return bestp;
		}
		
		private static void backtrack(int i)
		{
			if(i>n)
			{
				bestp=cp;
				return;
			}
			if(cw+w[i]<=c)
			{
				cw+=w[i];
				cp+=p[i];
				backtrack(i+1);
				cw-=w[i];
				cp-=p[i];
			}
			if(bound(i+1)>bestp)
				backtrack(i+1);
		}
		private static double bound(int i)
		{
			double cleft=c-cw;
			double bound=cp;
			while(i<n&&w[i]<=cleft)
			{
				cleft-=w[i];
				bound+=p[i];
				i++;
			}
			if(i<=n)
				bound+=p[i]*cleft/w[i];
			return bound;
		}
	}