转载

0-1背包问题

0-1背包问题

  • 问题描述

    给定 n n 个物品和一个背包, 物品 i i 的重量是 w i w_i ,价值是 v i v_i ,背包容量

    C C , 问如何选择装入背包的物品, 使得装入背包的物品的总价值

    最大?(针对某个物品,只能选择放入,或者不放入,不能部分放入)

  • 动态规划的两要素

    • 最优子结构

      通过分析,我们可以知道

      { x 1 , x 2 , x 3 , . . . x n } 假设\{x_1, x_2, x_3, ... x_n\} 是原问题的最优解

      x i = { 0 , 1 } x_i=\{0,1\} ,即针对第 i i 个物品可以选择放入为0,不放入为1

      则$ {x_2, x_3, x_4… x_n} ,是子问题:针对 i=2,3…n$个物品,背包

      容量为 C ? w 1 ? x 1 C-w_1*x_1 的最优解

      证明:

      如果 { x 2 , x 3 , x 4 . . . . x n } \{x_2, x_3, x_4....x_n\} 不是子问题的最优解,则存在另外一个 0 , 1 0,1 序列

      { g 2 , g 3 , g 4 . . . g n } \{g_2,g_3,g_4...g_n\} 是子问题的最优解,则 { x 1 , g 2 , g 3 , g 4 . . . g n } \{x_1, g_2, g_3, g_4...g_n\} 是比 { x 1 , x 2 , x 3 . . . x n } \{x_1, x_2, x_3...x_n\}

      更好的原问题最优解,与假设矛盾。

    • 子问题重叠

      F ( i , c ) F(i, c) 代表,针对后 i i ( { i , i + 1 , i + 2 , i + 3.... n } \{i, i+1, i+2, i+3....n\} ) 个物品,背包容量为 c c 的情况下,问题的最优解

      递归方程
      F ( i , c ) = F ( i + 1 , c )   c < w i F ( i , c ) = m a x { F ( i + 1 , c ) , F ( i + 1 , c ? w i ) + c i }   c > = w i F ( n , c ) = 0      c < w n F ( n , c ) = v n      c > = w n F(i,c)=F(i+1, c)\ c<w_i\\ F(i,c) = max\{F(i+1,c) , F(i+1, c-w_i)+c_i\}\ c>=w_i\\ F(n,c) = 0 \ \ \ \ c < w_n \\ F(n,c) = v_n \ \ \ \ c >= w_n

  • 代码实现

    • 题目链接leetcode 416

    • python代码

      class Solution(object):
          def canPartition(self, nums):
              """ :type nums: List[int] :rtype: bool """
              total = 0
              for number in nums:
                  total += number
              
              if total % 2 != 0:
                  return False
              
              #和的一半
              total = total / 2; n = len(nums)
      
              #矩阵
              F = [[False for i in range(total+1)] for j in range(n+1)]
              
              for i in range(1, n+1)[::-1]:
                  
                  for j in range(1, total+1):
                      
                      if i == n:
                          if j == nums[i-1]:
                              F[i][j] = True
                          else:
                              F[i][j] = False
                      else:
                          if F[i+1][j] == True:
                              F[i][j] = True
      
                          if j > nums[i-1] and F[i+1][j-nums[i-1]] == True:
                              F[i][j] = True
              
              return F[1][total]
      
  • 滚动数组,优化空间复杂度为 O ( n ) O(n)

    用一个一维的滚动数组 F [ c ] ? F[c]? ,来代替 F [ i ] [ c ] ? F[i][c]? ,重点是其递推顺序, c ? c? 应该变为逆序

    其中的 f [ c ] = m a x { f [ c ] , f [ c ? w i ] + v i } f[c] = max\{f[c], f[c?w_i]+v_i\} 一句恰就相当于我们的转移方程

    f [ i ] [ c ] = m a x { f [ i + 1 ] [ c ] , f [ i + 1 ] [ c ? w i ] + v i } f[i][c] = max\{f[i+1][c], f[i+1][c ? w_i]+v_i\}

    因为现在的 f [ c ? w i ] + v i f[c-w_i]+v_i 就相当于原来的 f [ i + 1 ] [ c ? w i ] + v i f[i + 1][c ?w_i]+v_i

    如果将 c c 的循环顺序从上面的逆序改成顺序的话,那么则成了 f [ i ] [ c ] f[i][c] f [ i ] [ c ? w i ] + v i f[i][c-w_i]+v_i 推知,与题意不符,

    改进后的python3代码

    class Solution:
        def canPartition(self, nums):
            """ :type nums: List[int] :rtype: bool """
            if(len(nums)) < 2: return False
            
            total = 0
            for i in range(len(nums)):
                total += nums[i]
                
            if total % 2 != 0: return False
            
            total = total // 2
            
            totalArr = [False for i in range(total + 1)]
            totalArr[0] = True
            
            for i in range(0, len(nums))[::-1]:
            
                for j in range(1, total+1)[::-1]:
                    
                    if j >= nums[i]:
                        totalArr[j] = totalArr[j] or totalArr[j-nums[i]]
            
            return totalArr[total]
    
正文到此结束
本文目录