Algorithm serial (1) - backpack problem of greedy

Piggy method: always make the best choice for current issues, that is, local search. Finally, the overall optimal is obtained.

Application: 1: This problem can be gradually transitioned to "Optimal" through "local search". The main difference between piggy choice and "dynamic planning".

2: Mostth Substand: The overall optimal solution of a problem contains the optimal solution of "sub" problem.

code show as below:

#include

Struct Goodinfo {FLOAT P; // Item Effect Float W; // Item Weight Float X; // The number of items should be placed int FLAG; // item number}; // item information structure

Void Insertionsort (GoodInfo Goods [], INT N) {Int J, I; For (J = 2; J <= N; J ) {GOODS [0] = Goods [J]; i = J-1;

While (Goods [0] .p> Goods [i] .p) {goods [i 1] = goods [i]; i-;} goods [i 1] = goods [0];}

} // According to the benefits of items, the weight ratio is arranged ascended

Void Bag (GoodInfo Goods [], Float M, INT N) {Float Cu; Int I, J; For (i = 1; i <= n; i ) Goods [i] .x = 0; Cu = m; / / Backpack remaining capacity for (i = 1; i cu) // When the weight is large and the remaining capacity is jumped out of Break; Goods [i] .x = 1; Cu = Cu-Goods [i] .w; // Determine new remaining capacity} if (i <= n) goods [i] .x = cu / goods [i] .w; // This item is put. the amount

/ * Declared in descending order * / for (j = 2; j <= n; j ) {goods [0] = goods [j]; i = j-1;

While (Goods [0] .flag

}

Void main () {cout << "| -------- Application greed method backpack problem --------- |" << Endl; cout << "| --- Power by zhanjiantao (028054115) --- | "<< endl; cout <<" | --------------------------------- ---- | "<< endl; int J; int N; float m; goodInfo * goods; // Define a pointer while (j) {cout <<" Please enter the total quantity of the item: "; cin >> N Goods = new struct goodinfo [n 1]; // cout << "Please enter the maximum capacity of the backpack:"; cin >> m; cout << Endl; Int i; for (i = 1; i <= n ; i ) {goods [i] .flag = i; cout << "Please enter the weight of the item" << "item:"; cin >> Goods [i] .w; cout << "Please enter "<< i <<" Benefits: "; cin >> Goods [i] .p; Goods [i] .p = Goods [i] .p / goods [i] .w; // The benefits of items, weight ratio cout << Endl;} insertions, n); BAG (Goods, M, N); cout << "Press <1> to run agi" << endl; cout << "Press < 0> to exit "<< Endl; CIN >> J;}}