背包问题 动态规划

背包问题

有n种物品,每种物品有自己体积(或价格或重量等等)c和价值w,每种物品可能有一个、可能有多个m、可能有无数个,我们有一个背包,背包的总体积为N,要求用这个背包装下价值尽可能多的物品,求该最大价值,背包可以不被装满。

根据物品的个数我们把背包问题分为0-1背包、多重背包和完全背包

背包问题通过动态规划方法解决,我们直接上一维dp的解决方法,dp[i]表示装了i体积物品的最大价值

0-1背包

每种物品只有一个,每个物品,我们可以装入背包也可以不装入背包

转移方程:

dp[i]=max(dp[i-c]+w, dp[i])

dp[i]表示没有装入背包的价值;dp[i-c]+w表示装入背包后的价值,需要给它挪出c的空间,所以有个i-c,它的价值为w,所以需要在dp[i-c]的基础上加上w

使用一维数组解决这个问题时,需要注意从后往前遍历整个体积,否则就会重复加入当前物品

for (int i=0; i < n; i++) { // 遍历n种物品
    for (int j = N; j>= goods[i].c;j--) { // 从后往前遍历背包体积
        dp[i] = max(dp[i-goods[i].c]+goods[i].w, dp[i]);
    }
}

完全背包

每个物品的数量有无穷个

其实,这个问题的解决方法很简单,就是在0-1背包的基础上从前往后遍历背包体积

0-1背包中为了避免重复加入某个物品,所以从后往前遍历

而完全背包中,每个物品的数量是无穷的,所以可以重复加入

for (int i=0; i < n; i++) { // 遍历n种物品
    for (int j = goods[i].c; j <= N; j++) { // 从后往前遍历背包体积
        dp[i] = max(dp[i-goods[i].c]+goods[i].w, dp[i]);
    }
}

多重背包

每个物品数量不定,所以我们得注意不能超过限制

转移方程:

dp[i]=max(dp[i- k * c]+ k * w, dp[i]),1<=k<=m

for (int i=0; i < n; i++) { // 遍历n种物品
    for (int k = 1; k <= goods[i].m; k++) { // 遍历物品个数
        for (int j = x; j >= k * goods[i].c;j--) { // 从后往前遍历背包体积
            dp[j] = max(dp[j- k * goods[i].c] + k * goods[i].w, dp[j]);
        }
    }
}
上一篇:laravel商品详情api


下一篇:FastAdmin 排坑之路