c语言解决完全背包问题

1.源码实现

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

/* 完全背包问题 
 * 完全背包问题可转化为01背包问题
 * w = 4, 5, 6, 3, 5 
 * v = 3, 4, 5, 3, 6
 * c = 10
 */

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

int main()
{
    int w[6] = {0, 3, 4, 5, 3, 6};
    int v[6] = {0, 4, 5, 6, 3, 5};
    int m[6][15];
    int ew[32];
    int ev[32];
    int em[32][16];
    int ex[32];
    int eu[32];
    int x[6];
    int en = 0;
    int n = 5;
    int c = 12;
    int ec = 12;
    int i, j;

    memset(ew, 0x00, sizeof(ew));
    memset(ev, 0x00, sizeof(ev));
    memset(em, 0x00, sizeof(em));
    memset(m, 0x00, sizeof(m));
    memset(x, 0x00, sizeof(x));

    j = 1;

    for(i=1; i<=5; i++)
    {
        c = ec;

        while(c > 0)
        {
            ew[j] = w[i];
            ev[j] = v[i];
            eu[j] = i;
            c -= w[i];
            en++;
            j++;
        }
    }

    for(i=1; i<=en; i++)
    {
        for(j=1; j<=ec; j++)
        {
            if(j >= ew[i])
            {
                em[i][j] = max(em[i-1][j], em[i-1][j-ew[i]]+ev[i]);
            }
            else
            {
                em[i][j] = em[i-1][j];
            }
        }
    }

    for(i=1; i<=en; i++)
    {
        for(j=1; j<=ec; j++)
        {
            printf("%d\t", em[i][j]);
        }

        printf("\n");
    }

    for(i=en; i>1; i--)
    {
        if(em[i][ec] == em[i-1][ec])
        {
            ex[i] = 0;
        }
        else
        {
            ex[i] = 1;
            ec -= ew[i];
        }

        ex[1] = (em[1][ec] > 0 ? 1 : 0);
    }

    for(i=1; i<=en; i++)
    {
        if(ex[i])
        {
            x[eu[i]]++;
        }
    }

    for(i=1; i<=en; i++)
    {
        printf("%d ", ex[i]);
    }
    
    printf("\n");

    for(i=1; i<=n; i++)
    {
        printf("%d ", x[i]);
    }

    printf("\n");

    return 0;
}

2.编译源码

$ gcc -o example examle.c -std=c89

3.运行及其结果

$ ./example
0   0   4   4   4   4   4   4   4   4   4   4   
0   0   4   4   4   8   8   8   8   8   8   8   
0   0   4   4   4   8   8   8   12  12  12  12  
0   0   4   4   4   8   8   8   12  12  12  16  
0   0   4   5   5   8   9   9   12  13  13  16  
0   0   4   5   5   8   9   10  12  13  14  16  
0   0   4   5   5   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
0   0   4   5   6   8   9   10  12  13  14  16  
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 
4 0 0 0 0