Lecția 33: Algoritmi euristici. Greedy

Exercițiu de Simulare: 33/2

Mar, 05/04/2021 - 17:52

Mai jos este la fel prezentat programul cu tehnica Greedy. De această dată sunt alte produse în listă. Volumul rucsacului trebuie să fie egal cu 11. Însă, cineva a șters o bucată de cod din program. Fixează acest program, efectuează schimbările corespunzătare și rulează programul.

#include <stdio.h>

struct produs
{
    int id;
    int cant;
    int cost;
    float pret;
};

int k;
float costrucsac;
struct produs tmp;

int n = 3; // 3 produse
int vstart, volumliber = 2;
struct produs p[100] =
{
    // id, cantitate, cost
    {1, 20, 10},
    {2, 5, 5},
    {3, 10, 7}
};

void selection_sort(struct produs x[], int n)
{
    int pmax;
    float max;

for (int j = n - 1; j >= 0; j--)
    {
        max = x[0].pret;
        pmax = 0;
        for (int i = 1; i <= j; i++)
            if(max > x[i].pret)
            {
                max = x[i].pret;
                pmax = i;
            }
        tmp = x[pmax]; x[pmax] = x[j]; x[j] = tmp;
    }
}

int main()
{
    // calculam coeficientul pentru fiecare produs
    // produsule sunt declarate in tabloul p
    for (int i = 0; i < n; i++)
    {
        p[i].pret = (float)p[i].cost / p[i].cant;
    }

// sortam elementele dupa coeficient descrescator
    selection_sort (p, n);

costrucsac = 0;
    k = 0;
    vstart = volumliber; // tinem minte volumul initial
    while (volumliber > 0 && k < n)
    {
        /*
            aici ceva lipseste
            impareca...
        */

k++;
    }

printf("Pentru rucsac cu volum = %d, costul maxim = %.2f", vstart, costrucsac);
    return 0;
}

Lecția 33: Algoritmi euristici. Greedy

Înregistrează-te la Newsletter