背包问题
1 问题描述
有N个商品，每个商品的体积是c[j], j = 1, 2, 3, .., N，每个商品的价值是v[j]， j = 1, 2, …, N.现在有一个背包，体积是C，现在要求往包里面装商品，使得在装得下的情况下，整包商品的价值最大。
2 问题求解的思路
2.1 子问题提取和描述
v[i, c], 当取的商品是{0, 1, 2, 3, …, i}的子集，最大体积是c时的最大商品总价值。原问题是，当商品是{1,2,3,…,N}的子集，最大体积是C时的商品的最大总价值，这里缩小了可选择的商品和容量的可选空间，提取子问题，可见这个子问题和原问题是同构的。
2.2 递推关系提取
初始值：
v[0, c] = 0
v[i, c] = -∞, c<0，这个时候方案是不存在的。
递推关系：
分成两类，选择i和不选择i。
不选择i，商品的最大总价值是v[i-1, c]；
选择i时，商品的最大总价值是v[i] + v[i-1, c-c[i]]
因此
v[i, c] = max{v[i-1, c], v[i] + v[i-1, c-c[i]]}
2.3 列表求解
例子：c[j] = {3, 5, 2, 7, 4}， v[j] = {2, 4, 1, 6, 5}
v[i, c] c = 0 1 2 3 4 5 6 7 8 9 10
i = 0 0 0 0 0 0 0 0 0 0 0 0
i = 1 0 0 0 2 2 2 2 2 2 2 2
i = 2 0 0 0 2 2 4 4 4 6 6 6
i = 3 0 0 1 2 2 4 4 5 6 6 7
i = 4 0 0 1 2 2 4 4 6 6 7 8
i = 5 0 0 1 2 5 5 6 7 7 9 9
所以，商品的最大价值是9。
3 编程实现
#include <iostream>
int max(int a, int b)
{
if (a > b)
{
return a;
} else {
return b;
}
}
int main(int argc, char* argv[])
{
int capacity[5] = {3, 5, 2, 7, 4};
int value[5] = {2, 4, 1, 6, 5};
int V[6][11] = {0};
for(int i = 1; i < 6; i++)
{
for (int j = 1; j < 11; j++)
{
if ((j – capacity[i]) < 0)
{
V[i][j] = V[i-1][j];
} else {
V[i][j] = max(V[i-1][j], V[i-1][j – capacity[i]] + value[i]);
}
}
}
std::cout<<“the max is:”<<V[5][10]<<std::endl;
}