乗船問題(欲張りアルゴリズム+反復解)


質問説明:n人がいて、i人目の重さはWiです.1隻の船の最大荷重はCで、最大2人を収容し、最小の船ですべての人を積む.

  
    
#include < iostream >
#include
< ctime >
#include
< algorithm >
using namespace std;
#define N 20 //
#define C 120 //
static int bcount = 0 ;

void boat_num( int weight[], int left, int right)
{
int first,j;
for ( int i = 0 ;i <= right;i ++ )
{
first
= weight[i]; //
for (j = i + 1 ;j <= right;j ++ )
if (weight[j] > C - first) // j C, j
{
cout
<< " "
<< j
<< " "
<< right
<< " " ;
bcount
+= right - j + 1 ; //
cout << bcount << endl;
break ;
}
cout
<< " " // j-1 ,
<< i
<< " "
<< j - 1
<< " " ;
bcount
++ ;
cout
<< bcount << endl;

right
= j - 2 ; // right j-2, 。
}
}

int main()
{
int weight[N];
srand((unsigned)time(NULL));
for ( int i = 0 ;i < N;i ++ )
weight[i]
= 40 + rand() % 60 ;

sort(weight,weight
+ N); //
for (i = 0 ;i < N;i ++ )
{
if (i > 0 && 0 == i % 10 )
cout
<< endl;
cout
<< weight[i] << " " ;
}
cout
<< endl;

boat_num(weight,
0 ,N - 1 ); //

cout
<< " "
<< bcount
<< " " << endl;
return 0 ;
}