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;
}
Recent Stories
Top DiscoverSDK Experts
Mendy Bennett
Experienced with Ad network & Ad servers.
Mobile | Ad Networks and 1 more
View Profile
Karen Fitzgerald
7 years in Cross-Platform development.
Mobile | Cross Platform Frameworks
View Profile
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
{{CommentsModel.TotalCount}} Comments
Your Comment