完全背包问题

之前已经讲解过0-1背包问题,今天来讨论另外一种:完全背包问题 1. 问题描述之前0-1背包问题的问题描述如下 给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大? 而今天要讨论的完全背包问题描述如下 给出n种物品的体积A[i]和其价值V[i],每一种物品都有无限个,将这n种物品装入一个大小为m的背包,最多能装入的总价值有多大? 我们可以发现区别在于:对于每一种物体,不再是之前0-1问题,而是0-k,k表示能放多个,k有可能是0,1,2…     阅读全文
Binbin Xu's avatar
Binbin Xu 2月 27, 2016

0-1背包问题

背包问题是一个非常经典的问题,今天我们就来讨论其中的一种:0-1背包问题 1. 问题描述 给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大? 为什么叫0-1背包问题呢,题目中假设每一种背包只有装和不装两种情况,我们不可能装入两个A[0]的物品,所以叫0-1背包问题 2. 转移方程我们构造一个二维的转移数组dp[i][j],表示前面i个物品放入总体积为j的背包中所获得的最大价值,那么:12dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]] + V[i]);// dp[i-1][j]表示不放入物品A[i], dp[i-1][j-A[i]] + V[i]表示放入物品A[i]所得到的最大价值     阅读全文
Binbin Xu's avatar
Binbin Xu 2月 25, 2016