https://run.codes/exercises/view/9974

baudafelicidade.c

/*
	Trabalho PAA - Baú da Felicidade
	É tipo knapsack, só que são duas mochilas, e o peso é igual ao valor :)
	Autor: Pedro Henrique Lara Campos (UFSCar RA 726578)
	Data: 2018-12-15
	https://run.codes/exercises/view/9974
*/
#include<stdio.h>
#include<stdlib.h>

#define DEBUG 0
#define METODO_RECURSIVO 0
#define METODO_PROGRAMACAO_DINAMICA 1
#define USE_METODO METODO_PROGRAMACAO_DINAMICA

#if DEBUG == 1
#define dprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define dprintf(...) // 1
#endif

unsigned int goldsack(unsigned int capacity, unsigned short *weights, unsigned char nbelem) {
	if (nbelem < 1  || capacity < 1)
		return 0;
#if USE_METODO == METODO_RECURSIVO
	unsigned short nthelem = weights[nbelem-1];
	if (nthelem > capacity)
		return goldsack(capacity, weights, nbelem-1);

	unsigned int a = nthelem + goldsack(capacity - nthelem, weights, nbelem-1),
		b = goldsack(capacity, weights, nbelem-1);

	return (a > b) ? a : b;
#else
	size_t cache_nbrow = (capacity+1),
		cache_nbelem = (nbelem+1) * cache_nbrow;

	unsigned short *cache =	(unsigned short *) calloc(cache_nbelem, sizeof(unsigned short));
	unsigned short *cache_nav,
		*cache_end=&cache[cache_nbelem];

	// POPULATE FIRST ROW
	/*unsigned short *cache_nav_end = &cache[cache_nbrow];
	dprintf("{%u,h}:\t", capacity);
	for (cache_nav = cache; cache_nav < cache_nav_end; cache_nav++) {
		// *cache_nav = 0; // ALREADY DONE IN CALLOC
		dprintf("%hu\t", *cache_nav);
	}*/

	// THE REST
	unsigned short *up_guy, *weight_nav, aux;
	size_t cell;

	up_guy = cache;
	cache_nav = &cache[cache_nbrow];
	weight_nav = weights;
	while (cache_nav < cache_end) {
		dprintf("\n{%u,%hu}:\t", weight_nav - weights, *weight_nav);
		
		// *cache_nav = 0; // ALREADY DONE IN CALLOC
		dprintf("%hu\t", *cache_nav);
		cache_nav++; up_guy++;
		
		cell = 1;
		while (cell <= capacity) {
			if (*weight_nav <= cell) {
				aux = *weight_nav + *(up_guy-(*weight_nav));
				*cache_nav = (aux > *up_guy ? aux : *up_guy);
			} else {
				*cache_nav = *up_guy;
			}
			dprintf("%hu\t", *cache_nav);

			cell++;
			cache_nav++;
			up_guy++;
		}

		weight_nav++;
	}
	dprintf("\n");

	// LET THE OS DO IT: free(cache);
	return *(cache_nav-1);
#endif
}

int main() {
	unsigned char coins_num;
	if(scanf("%hhu", &coins_num) != 1)
		return -1;
	dprintf("Size: %hhu\n", coins_num);

	unsigned short *coins = (unsigned short *) calloc(coins_num, sizeof(unsigned short));
	unsigned int total_value = 0, smaller_sack;

	unsigned short *coins_nav, *coins_end = &coins[coins_num];
	for(coins_nav = coins; coins_nav < coins_end; coins_nav++) {
		if(scanf("%hu", coins_nav) != 1) {
			fputs("Less coins than expected!\n", stderr);
			// LET THE OS DO IT: free(coins);
			return -2;
		}
		dprintf("%hu ", *coins_nav);
		total_value += *coins_nav;
	}
	dprintf("\n");
	
	smaller_sack = goldsack(total_value / 2, coins, coins_num);
	dprintf("Uma pilha de %u, e outra de %u.\n", smaller_sack, total_value-smaller_sack);
	printf("%u", total_value-smaller_sack-smaller_sack);

	// LET THE OS DO IT: free(coins);
	return 0;
}