动态规划-简易背包问题

老王装货.cpp

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

// 千里码刷题: http://www.qlcoder.com/task/7566

static const int goods[16] = {0, 509, 838, 924, 650, 604, 793, 564, 651, 697, 649, 747, 787, 701, 605, 644};

#define MAX(x, y) ((x) > (y)? (x) : (y))

int main(int argc, char * argv[])
{
    int sum[5001] = {0};

    for (int i = 1; i <= 15; i++) {
        for (int j = 5000; j >= 1; j--) {
            if (j >= goods[i]) {
                sum[j] = MAX(sum[j], sum[j - goods[i]] + goods[i]);
            }
        }
    }
    printf("max value %d\n", sum[5000]);

    int max = sum[5000];
    for (int i = 15; i >= 1; i--) {
        if (max >= goods[i]) {
            if ((sum[max] - sum[max - goods[i]]) == goods[i]) {
                printf("No.%d selected\n", i + 1);
                max -= goods[i];
            }
        }
    }
    
    system("pause");

    return 0;
}