AcWing 7. 混合背包问题    原题链接    中等

作者： 作者的头像   于于 ,  2022-03-29 22:47:14 ,  所有人可见 ,  阅读 371

5


二刷提高课，题解目录在这里— 提高课的题解目录

混合背包问题，我们对特定的背包进行特定的处理即可
但是这里如果全是多重背包可能会超时，所以需要使用优化
这里选择比较简单的二进制优化


#include<iostream>
using namespace std;
int f[1010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        if(s==-1)
        {
            for(int j=m;j>=v;j--)
            {
                f[j]=max(f[j],f[j-v]+w);
            }

        }
        else if(s==0)
        {
            for(int j=v;j<=m;j++)
            f[j]=max(f[j],f[j-v]+w);
        }
        else
        {
            for(int k=1;k<=s;k*=2)
            {
                for(int j=m;j>=k*v;j--)
                f[j]=max(f[j],f[j-k*v]+w*k);
                s-=k;
            }
            if(s)
            {
            for(int j=m;j>=s*v;j--)f[j]=max(f[j],f[j-s*v]+w*s);
            }
        }
    }
    cout<<f[m];
    return 0;
}

1 评论

用户头像
Dionysus.   2022-04-07 13:47         踩      回复

请问一下二维实现的代码是什么样子的啊，为什么这样一直WA啊

#include<iostream>
using namespace std;

const int N = 3100;

int f[N][N];

int main()
{
    int t,V;
    cin >> t >> V;

    for(int i = 1;i <= t;i ++ )
    {
        int v,w,s;cin >> v >> w >> s;

        if(s == 0)
        {
            for(int j = 1;j <= V;j ++ )
            {
                f[i][j] = f[i - 1][j];
                if(j >= v)f[i][j] = max(f[i][j],f[i - 1][j - v] + w);
            }
        }
        else
        {
            if(s == -1)
            {
                for(int j = 1;j <= V;j ++ )
                {
                    f[i][j] = f[i - 1][j];
                    if(j >= v)f[i][j] = max(f[i][j],f[i - 1][j - v] + w);
                }
            }
            else
            {
                int k = 1;
                for(int k = 1;k <= s;k *= 2)
                {
                    for(int j = 1;j <= V;j ++ )
                    {
                        f[i][j] = f[i - 1][j];
                        if(j >= k * v)f[i][j] = max(f[i][j],f[i - 1][j - k * v] + k * w);
                    }
                    s -= k;
                }
                if(s)
                {
                    for(int j = 1;j <= V;j ++ )
                    {
                          //f[i][j] = f[i - 1][j];
                        if(j >= s * v)f[i][j] = max(f[i][j],f[i][j - s * v] + s * w);
                    }
                }
            }

        }
    }

    cout << f[t][V];
    return 0;


}