题目描述

给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为 vi，背包容量为 C（也就是背包的总承重 C）。问，应如何选择装入背包的物品，使得背包的物品的总价值 V 最大化

分析

分析 0-1 背包问题最优解的结构特征

  1. 一种情况是第 n 个物品不包含在背包中
    设 x* = （x1,x2,x3,…,xn-1,xn）
    则（x1,x2,x3,…,xn-1）必为第 n-1 个物品（剔除第 n 个物品），且背包容易为 C 情况下的最优解
  2. 第二种情况是 n 个物品包含在背包中
    则（x1,x2,x3,…,xn-1）必为第 n-1 个物品，在背包容量为 C-wn 情况下的最优解

找出 0-1 背包问题最优解对应的最优值，并递归定义最优值

在 n 个物品中，背包容量为 C 情况下总价值，用 m(n,C)表示最优值

1
2
3
4
5
m(n,C) = {
  0,                              n=0或C=0
  max{m(n-1,C), m(n-1,C-wn)+vn}   wn<C
  m(n-1,C)                        wn>C
}

自底向上求最优值

根据 m 值矩阵得出最优解