さいてきローディング欲張りアルゴリズム
1443 ワード
問題の説明:
コンテナには重量cの汽船が積まれている.このうちコンテナiの重量はwiである.最適積載問題は、積載体積が制限されない場合に、できるだけ多くのコンテナを汽船に積み込むことを要求する.
解析:
この問題は次のように形式化されています.
max∑xi, 1 <= i <= n
∑wixi <= c, 1 <= i <= n
xi ∈{0, 1}, 1 <= i <= n
それは貪欲な2つの基本要素に合致する:1:貪欲な選択の性質(すなわち求めた問題の全体的な最適解は一連の局所的な最適な選択--貪欲な選択を通じて達成することができる)
2:最適サブ構造特性.
コード:
コンテナには重量cの汽船が積まれている.このうちコンテナiの重量はwiである.最適積載問題は、積載体積が制限されない場合に、できるだけ多くのコンテナを汽船に積み込むことを要求する.
解析:
この問題は次のように形式化されています.
max∑xi, 1 <= i <= n
∑wixi <= c, 1 <= i <= n
xi ∈{0, 1}, 1 <= i <= n
それは貪欲な2つの基本要素に合致する:1:貪欲な選択の性質(すなわち求めた問題の全体的な最適解は一連の局所的な最適な選択--貪欲な選択を通じて達成することができる)
2:最適サブ構造特性.
コード:
#include
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()
{
scanf("%d %d", &c, &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &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, 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();
}