乗船問題(欲張りアルゴリズム+反復解)
13268 ワード
質問説明: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
;
}