Java教程

0/1背包问题

本文主要是介绍0/1背包问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

0/1背包问题

背包问题(Knapsack Problem)是一类经典的动态规划问题,是一种组合优化的NP完全(NP-Complete, NPC)问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价值,在限定的总重量内,如何选择,才能使得物品的总价值最高。NPC问题是没有多项式时间复杂度的解法的,但利用动态规划,可以在伪多项式时间复杂度下求解背包问题。本文讨论的是背包问题中的最基本的0/1背包问题

问题描述

一共有N件物品,第i件物品的重量是w[i],价值是v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?

分析

如果采用暴力法,对于每件物品都有两种状态取或不取,时间复杂度为O(2^N),这是不可接受的。如果采用动态规划,则可以将复杂度降为O(N·W)。

我们的目标是背包内物品的总价值,而变量是物品和背包的当前重量,因此我们可以设状态dp:dp[i][j]表示考虑前i件物品且背包当前重量为j时的背包物品总价值。

那么,对于dp[0][0...W]初始化为0,表明考虑前0个物品后,背包物品总价值为0。当i>0时,dp[i][j]会有两种情况:

  1. 不装入第i件物品,则dp[i][j] = dp[i-1][j]
  2. 装入第i件物品,则dp[i][j] = dp[i-1][j - w[i]] + v[i]

此时,我们可以得到状态转移方程(j>=w[i]):dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

我们发现,dp[i][j]只和dp[i-1][0...j-1]有关,所以我们可以采用动态规划常用的方法“滚动数组”对空间进行优化,即去掉dp的第一维。需要注意的是,为了防止上一层循环的状态dp被覆盖,循环的时候 j 只能从尾部开始枚举。于是有了如下代码:

int dp[W] = {0};
for(int i = 1;i<=N;i++){
    for(int j = W-1;j>=w[i]-1;j--){
        dp[j] = max(dp[j], dp[j−w[i]]+v[i]);
    }
}

总结

利用动态规划解决0/1背包问题,时间复杂度为O(N·W), 空间复杂度为O(W)。由于W的值是W的位数的幂,所以这个时间复杂度是伪多项式时间。

动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定,暴力枚举忽略了这个事实。

这篇关于0/1背包问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!