原创声明：本文所有图片和代码皆由本人制作和编写。

前言

网上关于01背包动态规划的题解很多，重心大多都放在了状态转移方程上，而对于动态规划算法必须具备的2个特征并没有进行论证与阐述，本篇文章将从论证最优子结构与重叠子问题开始，利用动态规划法来解决01背包问题。

定义子问题

有n件物品和一个最多能背重量为w的背包。每件物品只能装入背包一次，求解将哪些物品装入背包里物品价值总和最大。

论证最优子结构

设（X1,X2, ... ,Xn）是0/1背包问题的最优解，证明（X2, ... ,Xn）是子问题：的最优解，其中，子问题有约束条件：

反证法：设子问题另有最优解（Y2, ... ,Yn）。
那么有：
所以有：
由子问题的第一个约束条件移项得：
综上，推出0/1背包问题的最优解是（X1,Y2, ... ,Yn）, 而这与题设矛盾，故假设不成立，即子问题不存在另外的最优解，所以（X2, ... ,Xn）就是子问题的最优解，0/1背包问题具备最优子结构。

阐述重叠子问题

对于第i个物品只有两种可能，能装与不能装。
不能装时，所求结果与“装前i-1个物品最优决策结果”一样，即重叠，不必重复计算。

所以，0/1背包问题具备最优子结构以及重叠子问题，可以考虑动态规划解法。

动态规划函数

继续考虑能装时的情况，所求结果在 “第i个物品价值 + 为第i个物品预留空间后的装前i-1个物品最优决策结果” 与 “不为第i个物品预留空间的装前i-1个物品最优决策结果”之间取最大值。
综上可设计动态规划函数：
设V(i,j)表示把前i个物品放入容量为j的背包可获得的最优结果。
则有递推式如下：

显然，只有当V(i,j) > V(i-1,j)时，第i件物品被放入了背包，否则，则没有放入。
故有：

算法流程图

算法实现

public int solveBag(){
	dpTable=new int[objectsNum+1][weightLimit+1];
        /*把第i个物品放入当前容量为0的背包*/
        for(int i=0 ;i < dpTable.length ; i++){
            dpTable[i][0] = 0;
        }
        /*把第0个物品放入当前容量为i的背包*/
        Arrays.fill(dpTable[0], 0);

        taken = new int[objectsNum];
        Arrays.fill(taken,0);
        for(int objectIndex = 1; objectIndex <= objectsNum; objectIndex++){
            for(int space=1; space <= weightLimit ; space++){
                if(objectsWeight[objectIndex - 1] > space){
                    dpTable[objectIndex][space] = dpTable[objectIndex-1][space];
                }else{
                    /*空间够，决策：空间要不要腾给当前物品，
                    比较：全部空间给前面物品的最优解 和
                         当前物品的价值 + 剩余空间给前面物品的最优解
                    取最大值*/
                    dpTable[objectIndex][space] =
                            Math.max(dpTable[objectIndex - 1][space],
                                    dpTable[objectIndex - 1][space - objectsWeight[objectIndex - 1]] + objectsValue[objectIndex - 1]);
                }
            }
        }
        maxWeight = dpTable[objectsNum][weightLimit];

        //回溯，查看每一件物品是否被装
        for(int i = objectsNum,space = weightLimit ; i>0 ; i--){
            if(dpTable[i][space] > dpTable[i-1][space]){
                space -= objectsWeight[i-1];
                taken[i-1] = 1;
                takenNum++;
            }
        }

        return maxWeight;
    }