背包问题（一）——01背包-凯发app官方网站

问题描述

有n件物品和一个容量为c的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的总重量和不超过背包容量，且价值总和最大。

问题分析

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

假如前k个物品放入背包容量c的背包中，可以获取最大价值是fv(k, c), 那么单独考虑第k个物品：
如果k放入背包中，那么此背包的价值 = 前k-1个物品放入背包容量为c-w[k]所获取最大价值 v[k]
如果k不放入背包中，那么此背包的价值 = 前k-1个物品放入背包容量为c所获取的最大价值
即：
fv(k, c) = max{fv(k-1, c), fv(k-1, c-w[k]) vk}

例如，现在有物品
p1(1,3), p2(2,3), p3(2,6), p4(3,8), p5(4,9)

^前k件物品
|
5-4| 3 6 9 11 14 17
4-3| 3 6 9 11 14 17
3-2| 3 6 9 9 12 12
2-2| 3 3 6 6 6 6
1-1| 3 3 3 3 3 3
---------------------------->背包容量
1 2 3 4 5 6

代码实现如下：

点击(此处)折叠或打开

int max(int a, int b);
int findmaxvalue_01packge(int *weight, int *value, int len, int cpt)
{
int *fvk_1; // 这里其实只需要一个数组就可以了，两个数组只是为了更清晰的看到每一层迭代过程
int *fvk;
int *tmp;
int maxvalue = 0;
int i, j;
fvk_1 = (int*)calloc(sizeof(int) * (cpt 1));
fvk = (int*)calloc(sizeof(int) * (cpt 1));
if (null == fvk || null == fvk_1)
{
if (fvk_1)
free(fvk_1);
if (fvk)
free(fvk);
return -1;
}
for (i = 1; i <= cpt; i)
{
if (i >= weight[0])
fvk_1[i] = value[0];
}
for (j = 1; j < len; j)
{
for(i = 1; i <= cpt; i)
{
fvk[i] = max(fvk_1[i], (i >= weight[j] ? value[j] fvk_1[i - weight[j]] : 0));
}
// swap fvk and fvk_1
tmp = fvk;
fvk = fvk_1;
fvk_1 = tmp;
}
maxvalue = fvk_1[cpt];
free(fvk);
free(fvk_1);
return maxvalue;
}

阅读(3164) | 评论(0) | 转发(0) |

上一篇：使用文件锁防止进程启动多个实例

下一篇：经典c面试题 -- 序列均衡

给主人留下些什么吧！~~

| | | | |

感谢所有关心和支持过chinaunix的朋友们