问题描述
有一批集装箱,要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
装载问题的形式化描述
算法描述
最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。
核心算法
Template
<class Type>
void Loading(int x
[ ], Type w
[ ], Type c
, int n
)
{
int *t
= new int [n
+1];
Sort(w
, t
, n
);
for (int i
= 1; i
<= n
; i
++) x
[i
] = 0;
for (int i
= 1; i
<= n
&& w
[t
[i
]] <= c
; i
++)
{x
[t
[i
]] = 1; c
-= w
[t
[i
]];}
}
完整算法
#include
<bits
/stdc
++.h
>
using namespace std
;
const int MAX
= 1024;
typedef struct Goods
{
int weight
;
int id
;
};
int x
[MAX
];
Goods g
[MAX
];
int c
, n
, loaded_n
;
void Input()
{
cout
<<"请输入载重和箱子个数：";
cin
>>c
>>n
;
cout
<<"请输入箱子的重量：";
for(int i
= 1; i
<= n
; ++i
)
{
cin
>>g
[i
].weight
;
g
[i
].id
= i
;
}
}
bool
compare(const Goods
&a
, const Goods
&b
)
{
return a
.weight
< b
.weight
;
}
void Loading()
{
loaded_n
= 0;
memset(x
, 0, sizeof(x
));
sort(g
+ 1, g
+ n
+1, compare
);
for(int i
= 1; i
<= n
&& c
>= g
[i
].weight
; ++i
)
{
x
[g
[i
].id
] = 1;
c
-= g
[i
].weight
;
++loaded_n
;
}
}
void Output()
{
cout
<< "装入了 " << loaded_n
<< " 件物品" << endl
;
cout
<< "分别是" << endl
;
for(int i
= 1; i
<= n
; ++i
)
if(x
[i
] == 1)
cout
<< i
<< " ";
}
int main()
{
Input();
Loading();
Output();
}
测试样例
输入 请输入载重和箱子个数：15 6 请输入箱子的重量：5 1 4 8 6 3
输出 装入了 4 件物品 分别是 1 2 3 6
