AcWing 7. 混合背包问题

2021-01-25 18:15

阅读：496

标签：mes end wing code mem const out 混合背包 01背包

#include
#include
#includeusing namespace std ;
const int N=1010;
int f[N],g[N],q[N];
int n,m;
int a[N];
int main() {
    cin>>n>>m;
    for(int i=1; i) {
        int v,w,s;
        cin>>v>>w>>s;
        if(s==0) { //完全背包
            for(int j=v; j)
                f[j]=max(f[j],f[j-v]+w);
        } else {
            if(s==-1)//如果是01背包
                s=1;//换成s就只有1
            memcpy(g,f,sizeof f);
            for(int j=0; j) {
                int hh=0,tt=-1;
                for(int k=j; kv) {
                    if(hhv)
                        hh++;
                    if(hhtt)
                        f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
                    while(hhw)
                        tt--;
                    q[++tt]=k;
                }
            }
        }
    }
    coutendl;
    return 0;
}

AcWing 7. 混合背包问题

标签：mes end wing code mem const out 混合背包 01背包

原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12003907.html

上一篇：《C# 爬虫破境之道》：概述

下一篇：requests库核心API源码分析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 7. 混合背包问题
文章链接：http://soscw.com/index.php/essay/46917.html

亲，登录后才可以留言！

AcWing 7. 混合背包问题

评论

热门文章

推荐文章

最新文章

置顶文章