2023年8月1日发(作者：)

动态规划0-1背包问题最优⼦结构的证明（包你看懂）背景刚刚考完《数据结构与算法分析》这门课的期末考试，其中有⼀道证明题——0-1背包问题最优⼦结构的证明。因为当时上课的时候便⽐较“懵懂”，复习时候也没有认真看（个⼈对于ppt的证明过程抱有疑惑，现在回过头来看只是省略了⼀些介绍⽽已……太过于遗憾），果然拉垮了。但是本着⾄少要做到考后100分，便百度搜了搜，结果发现很少有⼈能够简单明了地证明这个正确性，⾃⼰思考了⼀番，有了⾃⼰的答案。证明过程0-1背包问题： 给定n中物品和⼀个背包，物品i的重量是wi,其价值为vi,xi代表是否选择这个物品（xi=1或0），背包的容量为C。如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤？0-1背包问题等价于⼀个整数规划问题：nmax∑i=1vixi⎧∑i=1wixi≤C⎨⎩xi∈{0,1},1≤i≤n(∗)s.t.n最优⼦结构：原问题的最优解包含⼦问题的最优解。画重点了下边是证明：———————————————————————————————————————————————————————设(y1,y2,…,yn)是(∗)的⼀个最优解，则(y2,y3,…,yn)是下⾯⼦问题的最优解：maxi=2vixi∑n⎧∑i=2wixi≤C−w1y1⎨⎩xi∈{0,1},2≤i≤ns.t.n证明：（反证法）假设(z2,z3,…,zn)是上述⼦问题的最优解，即(y2,y3,…,yn)不是⼦问题的最优解——不存在最优⼦结构则：i=2viyii=2vizi≤n∑w1y1+i=2wizi≤C∑∑则有∑i=1nviyi≤i=2vizi+v1y1∑n说明(y1,z2,z3,…,zn)是⽐(y1,y2,y3,…,yn)更优的⼀个解，与原假设⽭盾！解决你的疑惑有的⼈会这么认为（我最开始也是这个疑惑）：假如⾯对第n个物品时候，背包剩余空间为5，此时第n个物品为占据空间6，价值为10的物品，可以将原来背包⾥⾯占据空间为1的，价值为2的物品换出来啊！并把第n个物品加进去，这样总价值多了10-2=8，这不就说明没有最优⼦结构了么？⽽实际上，当你不考虑第n个物品时候（即在⼦问题中），你的背包容量也是将第n个物品所占体积减去后的容量（记住这句话，看完后⾯后可以回来再体会⼀下）再看这个公式⎧∑i=2wixi≤C−w1y1⎨⎩xi∈{0,1},2≤i≤ns.t.n应该这样理解：当你⾯对所有n个物品时，选择了⼀号物品即y1=1时，他的⼦问题便是背包总空间减去w1y1时候，选择后n-1个物品的最优解。就像上⾯疑惑中举出的例⼦，说明总体最优解包含第n个物品，说明在选择前n-1个物品的最优解时（⼦问题），此时背包容量仅为最初容量减去6，并考虑此时的最优解，此时的最优解也⼀定不会包括那个被“替换”出去的占据空间为1的，价值为2的物品，因为选择这件物品的话，⾯对第n个物品最后的空间会为5，⽽⾮要求的6（总体最优解中⾯对第n个物品时候需要的剩余容量）。

2023年8月1日发(作者：)

动态规划0-1背包问题最优⼦结构的证明（包你看懂）背景刚刚考完《数据结构与算法分析》这门课的期末考试，其中有⼀道证明题——0-1背包问题最优⼦结构的证明。因为当时上课的时候便⽐较“懵懂”，复习时候也没有认真看（个⼈对于ppt的证明过程抱有疑惑，现在回过头来看只是省略了⼀些介绍⽽已……太过于遗憾），果然拉垮了。但是本着⾄少要做到考后100分，便百度搜了搜，结果发现很少有⼈能够简单明了地证明这个正确性，⾃⼰思考了⼀番，有了⾃⼰的答案。证明过程0-1背包问题： 给定n中物品和⼀个背包，物品i的重量是wi,其价值为vi,xi代表是否选择这个物品（xi=1或0），背包的容量为C。如何选择装⼊背包的物品，使得装⼊背包中物品的总价值最⼤？0-1背包问题等价于⼀个整数规划问题：nmax∑i=1vixi⎧∑i=1wixi≤C⎨⎩xi∈{0,1},1≤i≤n(∗)s.t.n最优⼦结构：原问题的最优解包含⼦问题的最优解。画重点了下边是证明：———————————————————————————————————————————————————————设(y1,y2,…,yn)是(∗)的⼀个最优解，则(y2,y3,…,yn)是下⾯⼦问题的最优解：maxi=2vixi∑n⎧∑i=2wixi≤C−w1y1⎨⎩xi∈{0,1},2≤i≤ns.t.n证明：（反证法）假设(z2,z3,…,zn)是上述⼦问题的最优解，即(y2,y3,…,yn)不是⼦问题的最优解——不存在最优⼦结构则：i=2viyii=2vizi≤n∑w1y1+i=2wizi≤C∑∑则有∑i=1nviyi≤i=2vizi+v1y1∑n说明(y1,z2,z3,…,zn)是⽐(y1,y2,y3,…,yn)更优的⼀个解，与原假设⽭盾！解决你的疑惑有的⼈会这么认为（我最开始也是这个疑惑）：假如⾯对第n个物品时候，背包剩余空间为5，此时第n个物品为占据空间6，价值为10的物品，可以将原来背包⾥⾯占据空间为1的，价值为2的物品换出来啊！并把第n个物品加进去，这样总价值多了10-2=8，这不就说明没有最优⼦结构了么？⽽实际上，当你不考虑第n个物品时候（即在⼦问题中），你的背包容量也是将第n个物品所占体积减去后的容量（记住这句话，看完后⾯后可以回来再体会⼀下）再看这个公式⎧∑i=2wixi≤C−w1y1⎨⎩xi∈{0,1},2≤i≤ns.t.n应该这样理解：当你⾯对所有n个物品时，选择了⼀号物品即y1=1时，他的⼦问题便是背包总空间减去w1y1时候，选择后n-1个物品的最优解。就像上⾯疑惑中举出的例⼦，说明总体最优解包含第n个物品，说明在选择前n-1个物品的最优解时（⼦问题），此时背包容量仅为最初容量减去6，并考虑此时的最优解，此时的最优解也⼀定不会包括那个被“替换”出去的占据空间为1的，价值为2的物品，因为选择这件物品的话，⾯对第n个物品最后的空间会为5，⽽⾮要求的6（总体最优解中⾯对第n个物品时候需要的剩余容量）。