九种背包问题
01背包问题
一种物品只能放入背包或者不放入，不可分割，只考虑物品体积不考虑物品质量，体积有限的背包如何携带价值做多的物品
#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;
}
