之前已经讲解过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…     阅读全文

背包问题是一个非常经典的问题，今天我们就来讨论其中的一种：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]所得到的最大价值     阅读全文