算法入门-完全背包

【模板】完全背包

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背包一样,时间复杂度都是
全部评论

相关推荐

小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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