混合背包模板——为什么最后一个点过不去?
  • 板块学术版
  • 楼主wangyongzhen
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/9/24 21:06
  • 上次更新2023/11/5 12:40:39
查看原帖
混合背包模板——为什么最后一个点过不去?
189602
wangyongzhen楼主2020/9/24 21:06
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int f[40005],n,m,w[40005],v[40005],tot=0;

bool fl[40005];

int main()
{
    int t1,t2,t3,t4;
    scanf("%d:%d%d:%d%d",&t1,&t2,&t3,&t4,&m); 
    n=(t3*60+t4)-(t1*60+t2);//转换为背包容量 
    for(int i=1;i<=m;i++)
    {
        int w1,v1,p;
        cin>>w1>>v1>>p;//代价 价值 和 数量/物品种类 
        if(p)//分类处理:如果是多重背包和 01背包 
        {
            for(int k=1;k<=p;k<<=1)//二进制分组 
            {
                v[++tot]=k*v1;
                w[tot]=k*w1;
                p-=k;
                fl[tot]=1;
            }
            if(p)
            {
                v[++tot]=p*v1;
                w[tot]=p*w1;
                fl[tot]=1;
            }
        }
        else//完全背包 
        {
            v[++tot]=v1;
            w[tot]=w1;
            fl[tot]=0;  
        }
    }
    for(int i=1;i<=tot;i++)
    {
        if(fl[i])//01背包 
        {
            for(int j=n;j>=w[i];j--)
            {
                f[j]=max(f[j],f[j-w[i]]+v[i]);
            }
        }
        else//完全背包 
        {
            for(int j=w[i];j<=n;j++)
            {
                f[j]=max(f[j],f[j-w[i]]+v[i]);
            }
        }
    }
    cout<<f[n];
    return 0;
}
2020/9/24 21:06
加载中...