算法入门-完全背包

【模板】完全背包

https://ac.nowcoder.com/acm/problem/226516

题意

  • n种物品,每种物品有vol和val,背包体积为v,每种物品可以有任意多个,求背包最大价值和背包恰好装满最大价值

思路

  • 01背包变种,更新第二维时需要重复更新,改变循环方向即可

AC代码

#include<bits/stdc++.h>
using namespace std;


int vol[1010],val[1010];
int dp1[202020],dp2[202020];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,v;
    cin >> n >> v ;
    for(int i=1;i<=n;i++) cin >> vol[i] >> val[i] ;
    for(int i=1;i<=n;i++){
        for(int j=vol[i];j<=v;j++){
            dp1[j]=max(dp1[j],dp1[j-vol[i]]+val[i]);
        }
    }    
    cout << dp1[v] << endl;

    memset(dp2,-0x3f3f3f3f,sizeof(dp2));
    dp2[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=vol[i];j<=v;j++){
            dp2[j]=max(dp2[j],dp2[j-vol[i]]+val[i]);
        }
    }    
    cout << max(dp2[v],0) << endl;
    return 0;
}

复杂度

  • 完全背包和01背包一样,时间复杂度都是
全部评论

相关推荐

06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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