By Ephraim | 2/2/2017 | C Programming

Greedy Algorithm for Minimal Squares

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

// this is a bubble sort, very slow, but only for demonstration purposes
void sort(int *a, size_t len)
{
    size_t i, j;
    for (i = 0; i < len; i++)
    {
        for (j = i+1; j < len; j++)
        {
            if (a[j] > a[i])
            {
                // swap 
                a[j] ^= a[i];
                a[i] ^= a[j];
                a[j] ^= a[i];
            }
        }
    }
}

// simulated heap - array, length
void heap(int *a, size_t len)
{
    size_t j;
    int e = a[0];
    for (j = 1; j < len; j++)
    {
        if (a[j] > e)
        {
            a[j-1] = a[j];
            a[j] = e;
        }
        else 
        {
            break;
        }
    }
}

// a is the list of numbers, b is the list of modifiers, len is the length
int *minimal_squares(int *a, int *b, size_t len)
{
    size_t i, e;
    // sort both
    sort(a, len);
    sort(b, len);
    // iterate over the modifiers
    for (i = 0; i < len; i++)
    {
        // find the largest number
        if (a[0] < b[i])
        {
            printf("Modifiers too large!\n");
            return a;
        }
        a[0] -= b[i];
        // keep the largest element on top
        heap(a, len);
    }
    return a;
}

{{CommentsModel.TotalCount}} Comments

Your Comment

{{CommentsModel.Message}}

Recent Stories

Top DiscoverSDK Experts

User photo
3355
Ashton Torrence
Web and Windows developer
GUI | Web and 11 more
View Profile
User photo
3220
Mendy Bennett
Experienced with Ad network & Ad servers.
Mobile | Ad Networks and 1 more
View Profile
User photo
3060
Karen Fitzgerald
7 years in Cross-Platform development.
Mobile | Cross Platform Frameworks
View Profile
Show All
X

Compare Products

Select up to three two products to compare by clicking on the compare icon () of each product.

{{compareToolModel.Error}}

Now comparing:

{{product.ProductName | createSubstring:25}} X
Compare Now