01背包问题

01背包问题是困扰我很久的问题,通过此次课程我学到了如何处理这一类问题,01背包问题讲述的是给你个固定空间的背包,还有N多物品,每个物品有他的价值和所占用的空间大小,我们要做到的是让背包存放最大价值。

下面有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,求能存放的物品的最大价值。

我们最有好用的算法是用矩阵来计算,但是费空间。

我们先计算出背包容量为1-10的情况下选取只有a物品的时候可获得的最大价值,结果显然如下

1 2 3 4 5 6 7 8 9 10
a 0 6 6 6 6 6 6 6 6 6

现在我们要做选取b物品的操作,当剩余背包容量可以存放b物品是,我们先定义好不存在的数值为0,可以得到value1=a{剩余空间-b物品空间}+b.value,当剩余容量不足以存放b或者不选择b的时候,value2=a{剩余空间},取最大值即:max{value1,value2}得到的数值存入数组,当剩余背包容量为1-10时 如下所示,转折点为背包容量为2和背包容量为4的时候:

1 2 3 4 5 6 7 8 9 10
b 0 6 6 9 9 9 9 9 9 9

当剩余空间为2的时候,value1=3,value2=6,所以从空间为2开始就得到数据6,当剩余空间为4,value1=a{4-2}+b.value=6+3=9,故而数据开始变化,因为ab都放下了,故而后面数据不变,以此类推,得到下面数据:

1 2 3 4 5 6 7 8 9 10
c 0 6 6 9 9 9 9 11 11 14
d 0 6 6 9 9 9 10 11 13 14
e 0 6 6 9 9 12 12 15 15 15

由此可以得出,当背包空间为10的时候,得到的最大价值为15,选取物件为:a,b,e,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<string.h>
int main()
{
intweight[]={2,2,6,5,4},value[]={6,3,5,4,6},table[5][11],m=10;
memset(table,0,sizeof(table));
for(inti=0;i<5;i++){
for(intj=1;j<=m;j++){
if(j-weight[i]>=0){
if(i==0)table[i][j]=value[i];
else{
int a=table[i-1][j-weight[i]]+value[i];
int b=table[i-1][j];
table[i][j]=a>b?a:b;
}
}else if(i==0){}
else table[i][j]=table[i-1][j];
}
}
printf("%d",table[4][10]);
return 0;
}