bag.cpp

来自「利用回溯法求解背包问题和全排列的算法」· C++ 代码 · 共 54 行

#include<iostream>
using namespace std;
class beibao
{
	friend int aa(int *a,int m,int n);
   private:
      int  * x;
      void diedai(int);
      int m;
      int n;
      int bestw;
      int h;
	  int * s;
	  int shengyu;


};
void beibao::diedai(int i)
{
 
    if (i>=n)
    { 
		if (h>bestw)
			bestw=h;
       return;
    }
	else{
		if (h+x[i]<m)
		{   h=h+x[i]; 
	    	diedai(i+1);
  		    h-=x[i];
		}
    	diedai(i+1);

	};

};
int  aa(int *a,int m,int n)
{  beibao A;
  A.h=0;
  A.m=m;
  A.n=n;
  A.shengyu=m;
  A.x=a;
  A.s=new int [n];
  A.diedai(0);
  return A.bestw;
}
void main()
{
	int  a[10]={43,43,1,34,23,12,21,32,12,12};

	cout<<aa(a,175,10);
}