0-1 bag problem

bag.c

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

/* https://zhuanlan.zhihu.com/p/345364527 */

static inline int max(int a, int b)
{
    return a > b ? a : b; 
}

static int part_diff(int *nums, int numsSize)
{
    int sum = 0;
    for (i = 0; i < numsSize; i++) {
        sum += nums[i];
    }

    int *dp = malloc((sum / 2 + 1) * sizeof(int));
    memset(dp, 0, (sum / 2 + 1) * sizeof(int));

    for (i = 0; i < numsSize; i++) {
        int thing = nums[i]; /* the weight of the i-th thing */
        for (cap = sum / 2; cap >= thing; cap--) {
            /* check value of (i-1) things in bag[capacity] */
            /* bag[cap] means value of (i-1) things without the i-th thing */
            /* bag[cap - thing] means value of (i-1) things within the i-th thing */
            dp[cap] = max(dp[cap], dp[cap - thing] + thing);
        }
    }

#if 0
    for (i = 0; i <= sum / 2; i++) {
        printf("%d ", dp[i]);
    }
    printf("\n");
#endif
    return sum - 2 * dp[sum / 2];
}

int main(int argc, char **argv)
{
    if (argc < 2) {
        fprintf(stderr, "Usage: ./test target n1 n2...\n");
        exit(-1);
    }

    int i, count = argc - 1;
    int *nums = malloc(count * sizeof(int));
    for (i = 0; i < count; i++) {
        nums[i] = atoi(argv[i + 1]);
    }

    printf("%d\n", part_diff(nums, count));
    return 0;
}