允接上一文章内容：
算法 动态规划: link.
问题分析
按照普通思维，首先想到应该为贪心算法，也就是计算每个物品重量价值比，将性价比高的物品装入背包，但是这并不是该问题的最优解，因为物品不是可分割的，不能按照重量价值比进行选择
这道问题的最优解应该通过动态规划求解，那么其递归方程式为：
在这里f(i,j)，记为当背包容量为 j，现有 i 物品可拿，所能装进背包的最大价值
再者我们举例说明，假设背包总容量为8，现在有四件物品，其重量，价值分别为：
| 重量 | 价值 |
|---|---|
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
| 5 | 8 |
首先我们是一个 f(4,8)，即当容量为8，有4件物品可拿，所能装进背包的最大价值，接着第二步，选择对第四件物品拿与不拿，继而得到②③，f(3,3)+8，即容量为3，有 3 件物品可拿的最大价值加上 8（第四件物品的价值），或者 f(3,8)，容量 8，有 3 件物品可拿的最大价值
随着我们的不断细分，最终得到最大值为12，也就是拿走第二件与第四件物品，对于上面的方式，无论是从后往前拿还是从前往后拿都是相同的
那么我们再看上面的递归方程式就很明了了
代码实现
从前往后拿，递归实现
int Knapsack(vector<int>& w, vector<int>& v, int i, int j, int n)
{
if (i == n) //只有一个物品
{
return j >= w[i] ? v[i] : 0;
}
else
{
if (j < w[i]) //背包容量不足
{
return Knapsack(w, v, i + 1, j, n);
}
else
{
int maxv1 = Knapsack(w, v, i + 1, j, n); //不装该物品
int maxv2 = Knapsack(w, v, i + 1, j - w[i], n) + v[i]; //装该物品
return maxv1 > maxv2 ? maxv1 : maxv2;
}
}
}
int main()
{
const int n = 5; //物品数量
const int c = 10; //背包容量
vector<int> w = { 0,2,2,6,6,4 }; //重量
vector<int> v = { 0,6,3,5,4,6 }; //价值
int maxv = Knapsack(w, v, 1, c, n);
//i j
cout << maxv << endl;
return 0;
}
非递归实现
void print_vect(const vector<vector<int>>& m)
{
for (int i = 1; i < m.size(); ++i)
{
for (int j = 1; j < m[i].size(); ++j)
{
printf("%4d", m[i][j]);
}
printf("\n");
}
printf("\n");
}
int Knapsack2(vector<int>& w, vector<int>& v, int n, int c, vector<vector<int>>& m)
{
if (n == 0) return 0;
for (int j = 0; j <= c; ++j) //填充最后一行
{
m[n][j] = j >= w[n] ? v[n] : 0;
}
print_vect(m);
for (int i = n - 1; i >= 1; --i)
{
for (int j = 1; j <= c; ++j)
{
if (j >= w[i])
{
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
//通过容量与价值进行判断
}
else
{
m[i][j] = m[i - 1][j];
}
}
print_vect(m);
}
}
int main()
{
const int n = 5; //物品数量
const int c = 10; //背包容量
vector<int> w = { 0,2,2,6,6,4 }; //重量
vector<int> v = { 0,6,3,5,4,6 }; //价值
vector<vector<int>> m(n + 1, vector<int>(c + 1, 0));
Knapsack2(w, v, n, c, m);
return 0;
}
return 0;
}
在非递归实现中，我们首先传入了一个表格，其格式如下：
进入函数第一步，对最后一行进行填充，接下来自下向上每一行进行填充
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
在填充过程中，例如黄色位置：j >= w[i]，但是通过价值比较，4<6所以依然填入的是6，一直到 9 位置，10>6 则在此填入10
非递归实现，自上向下填充
void print_vect(const vector<vector<int>>& m)
{
for (int i = 1; i < m.size(); ++i)
{
for (int j = 1; j < m[i].size(); ++j)
{
printf("%4d", m[i][j]);
}
printf("\n");
}
printf("\n");
}
void Knapsack3(vector<int>& w, vector<int>& v, int n, int c, vector<vector<int>>& m)
{
for (int i = 1; i <= n; ++i) //行
{
for (int j = 1; j <= c; ++j) //列
{
if (j < w[i])
{
m[i][j] = m[i - 1][j]; //拷贝上面的
}
else
{
m[i][j] = std::max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
//判断放与不放的最优解
}
}
print_vect(m);
}
}
int main()
{
const int n = 5; //物品数量
const int c = 10; //背包容量
vector<int> w = { 0,2,2,6,6,4 }; //重量
vector<int> v = { 0,6,3,5,4,6 }; //价值
vector<vector<int>> m(n + 1, vector<int>(c + 1, 0));
Knapsack3(w, v, n, c, m);
return 0;
}
最后的代码是，通过上述表中的变化，对每个物品加上bool值来确定是否取走了该物品
void backx(vector<int>& w, vector<vector<int>>& m, int n, int c,vector<bool>& x)
{
for (int i = n; i >= 1; --i)
{
if (m[i][c] != m[i - 1][c]) //该物品放入了背包
{
x[i] = true;
c = c - w[i];
}
}
}
int main()
{
const int n = 5; //物品数量
const int c = 10; //背包容量
vector<int> w = { 0,2,2,6,6,4 }; //重量
vector<int> v = { 0,6,3,5,4,6 }; //价值
vector<vector<int>> m(n + 1, vector<int>(c + 1, 0));
vector<bool> X(n + 1,false);
Knapsack3(w, v, n, c, m);
backx(w, m, n, c, X);
for (int i = 1;i<=n;++i)
{
if (X[i])
{
cout << i << endl;
}
}
return 0;
}
