AcWing 5. 多重背包问题 II    原题链接    中等

作者： 作者的头像   fedfan ,  2020-03-05 18:00:01 ,  所有人可见 ,  阅读 6135

36


18

2020-03-05_175424.png
2020-03-05_175446.png
2020-03-05_175526.png
2020-03-05_175620.png

时间复杂度o(Nlogs1v)

二进制优化将n种物品，每种Si个的多重背包，拆分打包看成N件物品(组)的01背包问题
2000=1+2+4+…+2^9+c,所以最多11*1000件物品
不能用完全背包的优化方式优化多重背包，因为每种数目不是无限的

#include<iostream>
using namespace std;
const int N=11010,M=2010;
int n,m;
int v[N],w[N];
int f[M];
int main()
{
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++)//拆分打包
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)
        {
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
            cnt++;
        }
        if(s>0)
        {
            v[cnt]=s*a;
            w[cnt]=s*b;
            cnt++;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

13 评论

用户头像
witt   2023-02-28 17:17      1    踩      回复

看了好多篇不知道为什么开N=11e3+10，终于在这里看明白了

用户头像
嚯嚯哈嘿   9个月前         踩      回复

```cpp
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N = 2010;
int f[N],vv[N],ww[N];

int main() {
int n, m;
scanf(“%d%d”,&n,&m);

int num=1;//拆分的组数的计数
for(int i=1;i<=n;i++){
    int v,w,s;
    scanf("%d%d%d",&v,&w,&s);

    //这段代码本质是将原本的3种物品根据二进制拆分为10种物品
    for(int j=1;j<=s;){
        vv[num]=j*v;//体积
        ww[num++]=j*w;//价值
        s-=j;
        j*=2;
    }
    if(s){//若有剩余
        vv[num]=s*v;
        ww[num++]=s*w;
    }
}

//拆分为01背包后使用01背包模板即可
for (int i = 1; i < num; i++)
    for (int j = m; j >= vv[i]; j--) 
        f[j] = max(f[j], f[j - vv[i]] + ww[i]);

printf("%d",f[m]);
return 0;

}```
这个为什么测试数据都能过，但是一提交就过不了

用户头像
嚯嚯哈嘿   9个月前         踩      回复

```cpp
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
const int N = 2010;
int f[N],vv[N],ww[N];

int main() {
int n, m;
scanf(“%d%d”,&n,&m);

int num=1;//拆分的组数的计数
for(int i=1;i<=n;i++){
    int v,w,s;
    scanf("%d%d%d",&v,&w,&s);

    //这段代码本质是将原本的3种物品根据二进制拆分为10种物品
    for(int j=1;j<=s;){
        vv[num]=j*v;//体积
        ww[num++]=j*w;//价值
        s-=j;
        j*=2;
    }
    if(s){//若有剩余
        vv[num]=s*v;
        ww[num++]=s*w;
    }
}

//拆分为01背包后使用01背包模板即可
for (int i = 1; i < num; i++)
    for (int j = m; j >= vv[i]; j--) 
        f[j] = max(f[j], f[j - vv[i]] + ww[i]);

printf("%d",f[m]);
return 0;

}```
这个为什么测试数据都能过，但是一提交就过不了

用户头像
学不会动态规划不改名   2022-12-28 16:35         踩      回复

代码中间不是都把v[i]累加起来了吗 ，v[i]=ka;w[i]=kb;
怎么表示一个数啊，不是都加起来了吗

用户头像
小笨   2022-08-01 16:00         踩      回复 
if(s>0)
        {
            v[cnt]=s*a;
            w[cnt]=s*b;
            cnt++;
        }

各位大佬，这里cnt为什么还要++呢

用户头像
Fury_   2022-08-30 14:09      2    踩      回复

因为前面的物品数量s还有剩，不能被2的幂完整地减完，还剩下一部分，单独打包成一份，而cnt就是最终打包出来地数量，因此单独打包地那一部分也需要让cnt++

用户头像
声起于形   9个月前    回复了 Fury_ 的评论         踩      回复

s大于0，不就是有剩余吗，while循环已经给cnt加过了，if只是判断还有没有剩余，为什么这个地方还要再加一次

用户头像
张李浩   2021-09-05 14:27         踩      回复

顶！

用户头像
zad456   2021-06-05 21:00         踩      回复

厉害了，请问佬这个ppt是哪里的？

用户头像
天才美少女卡莎   2021-03-30 23:10         踩      回复

牛逼

用户头像
fedfan   2021-03-31 21:54         踩      回复

我菜鸡。。。

用户头像
小王又AF了   2021-03-27 18:11         踩      回复

强

用户头像
小王又AF了   2021-03-27 18:11         踩      回复

qp