完全背包问题

完全背包问题

\(\begin{cases}dp[0][j]=0\\dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i]) \end{cases}\)

代码:

int n,W;    cin >> n >> W;
for(int i=0;i<n;++i)
    for(int j=0;j<=W;++j)
        for(int k=0;k*w[i]<=j;++k)
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
int ans=dp[n][W];

但是这个算法的复杂度达到了\(O(nW^2)\),发现有一不部分计算可以利用前面计算的结果来简化,因此经过精简后的代码:

for(int i=0;i<n;++i)
    for(int j=0; j<=W; ++j)
        if(j<w[i]) dp[i+1][j]=dp[i][j];
        else dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
ans=dp[n][W];

同时出于节省内存的考虑,可以将其用一维数组表示

for(int i=0;i<n;++i)
    for(int j=w[i];j<=W;++j)
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
ans=dp[W];

也放出01背包的代码,对照一下:

for(int i=0;i<n;++i)
    for(int j=W;j>=w[i];--j)
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
ans=dp[W];

除此之外,因为递推方程只涉及\(dp[i]\)\(dp[i+1]\)之间的关系,所以可以将两个数组滚动使用

代码:

int dp[2][maxn];
for(int i=0;i<n;++i)
    for(int j=0;j<=W;++j)
        if(j<w[i]) dp[(i+1)&][j]=dp[i&1][j];
        else dp[(i+1)&1][j]=max(dp[i&1][j],dp[(i+1)&1][j-w[i]]+v[i]);
全部评论

相关推荐

CARLJOSEPH...:宝宝你戾气太大了
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务