九种背包问题

01背包问题

一种物品只能放入背包或者不放入，不可分割，只考虑物品体积不考虑物品质量，体积有限的背包如何携带价值做多的物品

AcWing题目地址

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

/**
 * f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
 * 1. 不选第i个物品 f[i][j] = f[i-1][j]
 * 2. 选第i个物品 f[i][j] = f[i-1][j-volume[i]] + value[i] 
 * f[i][j] = max(1,2);
 * f[0][0] = 0;
 */
int bag(int *volumes, int *values, int capacity);

int main(const int argc, const char **argv) {
    int size, capacity;
    while (scanf("%d %d",&size,&capacity)!=EOF) {
        /**
         * 数组第一个元素保存数组长度
         */
        int *volumes = (int *) calloc(size+1, sizeof(int));
        int *values = (int *) calloc(size+1, sizeof(int));
        values[0] = volumes[0] = size;
        for (int i=1;i<=size;i++) scanf("%d %d",volumes+i,values+i);
        int ret = bag(volumes,values,capacity);
        printf("%d\n",ret);
        free(volumes);
        free(values);
    }
    return 0;
}

int bag(int *volumes, int *values, int capacity) {
    int length = volumes[0];
    int **bags = (int **) calloc(length+1, sizeof(int *));
    for (int i=0;i<=length;i++) bags[i] = (int *) calloc(capacity+1, sizeof(int));
    bags[0][0] = 0;
    for (int i=1;i<=length;i++) {
        for (int j=0;j<=capacity;j++) {
            /**
             * 第i个物品是否放入背包，如果不放入背包
             */
            bags[i][j] = bags[i-1][j];
            /**
             * 第i个物品体积小于背包剩余体积，才能放入背包
             */
            if (j>=volumes[i]) 
                bags[i][j] = fmax(bags[i][j],bags[i-1][j-volumes[i]]+values[i]);
        }
    }
    int ret = 0;
    for (int i=0;i<=capacity;i++) ret = fmax(bags[length][i],ret);
    for (int i=0;i<length;i++) free(bags[i]);
    free(bags);
    return ret;
}

优化之后

int bag(int *volumes, int *values, int capacity) {
    int length = volumes[0];
    int *bags = (int *) calloc(capacity+1, sizeof(int));
    for (int i=1;i<=length;i++) {
        for (int j=capacity;j>=volumes[i];j--) {
            bags[j] = fmax(bags[j],bags[j-volumes[i]]+values[i]);
        }
    }
    int ret = bags[capacity];
    free(bags);
    return ret;
}