prog_gr.cpp

用遗传算法解决01背包问题

// Copyright by Guo Ce, Sun Yat-sen University

#include <vcl.h>
#include <stdlib.h>
#include "comdef.cpp"

//---------------------------------------------------------------------------
typedef struct Item
{
    int weight;
    int value;
} ITEM;

//---------------------------------------------------------------------------
extern int gene_length;
extern int bag_capacity;
extern ITEM items[MAXITEMS];

int result;

//---------------------------------------------------------------------------
void textout (AnsiString s);


//---------------------------------------------------------------------------
void run_greedy (void);


//---------------------------------------------------------------------------
int itemcmp (const void *px, const void *py)
{
    double vx = (double)(((ITEM*)px)->value) / (((ITEM*)px)->weight);
    double vy = (double)(((ITEM*)py)->value) / (((ITEM*)py)->weight);

    if (vx < vy)
        return 1;
    return -1;
};

void run_greedy (void)
{
    int i, rcnt, rw;

    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("贪心算法计算中，以下列出性价比排序结果：");
    qsort (items, gene_length, sizeof(items[0]), itemcmp);
    for (i=0; i<gene_length; i++)
        textout ("重量：" + IntToStr(items[i].weight) + "  价值：" + IntToStr(items[i].value));

    result = 0;
    rw = 0;
    rcnt = 0;
    for (i=0; i<gene_length; i++)
    {
        if (rw+items[i].weight>bag_capacity)
            break;
        result += items[i].value;
        rw += items[i].weight;
        rcnt ++;
    }

    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("贪心算法运行完毕。");
    textout ("取排序结果的前" + IntToStr(rcnt) + "件物品。");
    textout ("总价值：" + IntToStr(result));
    textout ("总重量：" + IntToStr(rw));
    textout ("- - - - - - - - - - - - - - - - - - - - - - - - -");
    textout ("");
    return;
}