0


动态规划-背包问题-完全背包

文章目录

题目描述

对比01背包,完全背包中的每件物品有无数件。

也就是说,每件物品可以拿0,1,…,k,…件。

状态(和01背包一样)

dp[i][j]表示前i种物品,体积为j时的最大价值

状态转移

  • 对于第i件物品: - 不拿:dp[i][j]⇐dp[i-1][j]- 拿一件:dp[i][j]⇐dp[i-1][j-w[i]]+v[i]- 拿两件:dp[i][j]⇐dp[i-1][j-2w[i]]+2v[i]- …- 拿k件:dp[i]][j]⇐dp[i-1][j-kw[i]]+kv[i]

状态转移方程

  •                                     d                            p                            [                            i                            ]                            [                            j                            ]                            =                            m                            a                            x                            (                            d                            p                            [                            i                            −                            1                            ]                            [                            j                            ]                            ,                            d                            p                            [                            i                            −                            1                            ]                            [                            j                            −                            k                            ∗                            w                            [                            i                            ]                            ]                            +                            k                            ∗                            w                            [                            i                            ]                            )                            ,                            k                            =                            1                            ,                            .                            .                            .                            ,                                       j                                           w                                  [                                  i                                  ]                                                       dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*w[i]),k=1,...,\frac{j}{w[i]}                     dp[i][j]=max(dp[i−1][j],dp[i−1][j−k∗w[i]]+k∗w[i]),k=1,...,w[i]j​
    
  • 展开 d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w [ i ] ] + v [ i ] , d p [ i − 1 ] [ j − 2 ∗ w [ i ] ] + 2 ∗ v [ i ] , . . . ) ( 1 + j w [ i ] 项 ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i],dp[i-1][j-2w[i]]+2v[i],...)(1+\frac{j}{w[i]}项) dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i],dp[i−1][j−2∗w[i]]+2∗v[i],...)(1+w[i]j​项)
  •                                     d                            p                            [                            i                            ]                            [                            j                            −                            w                            [                            i                            ]                            ]                            =                            m                            a                            x                            (                            d                            p                            [                            i                            −                            1                            ]                            [                            j                            −                            w                            [                            i                            ]                            ]                            ,                            d                            p                            [                            i                            −                            1                            ]                            [                            j                            −                            2                            ∗                            w                            [                            i                            ]                            ]                            +                            ∗                            v                            [                            i                            ]                            ,                            .                            .                            .                            )                            (                                       j                                           w                                  [                                  i                                  ]                                                 项                            )                                  dp[i][j-w[i]]=max(dp[i-1][j-w[i]],dp[i-1][j-2*w[i]]+*v[i],...)(\frac{j}{w[i]}项)                     dp[i][j−w[i]]=max(dp[i−1][j−w[i]],dp[i−1][j−2∗w[i]]+∗v[i],...)(w[i]j​项)
    
  • 综上可得dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])
  • 直观上理解为:前一项表示不取第i种,后一项表示在先前的基础上取第i种(取多次)

代码

n,V=map(int,input().split())
dp=[[0]*(V+1)for _ inrange(n+1)]for i inrange(1,n+1):
    w,v=map(int,input().split())for j inrange(V+1):if j<w:
            dp[i][j]=dp[i-1][j]else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-w]+v)print(dp[n][V])

滚动数组优化

…i-1,ji,j-w[i]i,j
可见,更新dp[i][j]时,用的是同一行先前位置dp[i][j-w[i]]和上一行对应位置的dp[i-1][j],和01数组不同在于更新方向。

使用单个数组更新时,采用从小到大的方向对dp数组进行覆盖。

n,V=map(int,input().split())
dp=[0]*(V+1)for i inrange(1,n+1):
    w,v=map(int,input().split())for j inrange(w,V+1):
        dp[j]=max(dp[j],dp[j-w]+v)print(dp[V])

本文转载自: https://blog.csdn.net/m0_73676887/article/details/136136976
版权归原作者 sml_5421 所有, 如有侵权,请联系我们删除。

“动态规划-背包问题-完全背包”的评论:

还没有评论