首页 > 代码库 > Codeforces 106 C Buns【多重背包】

Codeforces 106 C Buns【多重背包】

今天拉了一场CF,做了一下,略坑啊、、、首先105A题,竟然卡精度,小数点两位卡精度,需要给他加一个1e-6,算是见识了


题目:Codeforces 106 C Buns


题意:给出一些n克面,以及m种馅儿,每种馅儿做面包需要的面的克数和馅儿的克数以及馅儿的总克数,面也可以单独做面包,然后每一种面包都有价格,求做的面包的总价格最高?


分析:很贱的题目啊,读了之后就开始贪心,贪心竟然过了10组数据,然后我以为有漏洞,后来发现是个多重背包。dp的题目最怕用贪心做了,幸亏发现了。

标准的多种背包,转化一下就行了,n克面就是背包容量,然后每种的数量是馅儿的总量 / 每个的,花费是面的克数,价值是价格。剩下的事情就是模板了、二进制优化一下


AC代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1200;
struct Node
{
    int cost,w,nk; //价格,重量,代数
};
Node num[N];
int dp[N];
//int cmp(Node a,Node b)
//{
//    if(a.p!=b.p)
//    {
//        return a.p>b.p;
//    }
//}
void one(int cost , int w, int m)
{
    for(int i=cost ; i<=m; i++)
        dp[i] = max(dp[i] , dp[i - cost ]+w);
}
void zero_one(int m ,int w, int cost)
{
    for(int i=m; i>=cost; i--)
        dp[i]=max(dp[i],dp[i-cost]+w);
}
int main()
{
    int n,m,a,b;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    num[0].nk=n/a,num[0].cost=b,num[0].w=a;
    for(int i=1; i<=m; i++)
    {
        int x,y,z,h;
        scanf("%d%d%d%d",&x,&y,&z,&h);
        num[i].nk=x/y;
        num[i].cost=h,num[i].w=z;
    }
    for(int i=0; i<=m; i++)
    {
        int w=num[i].cost , cost=num[i].w, nk=num[i].nk;
        if(cost * nk >= n) one(cost , w  , n);
        else
        {
            int k = 1;
            while( k < nk)
            {
                zero_one(n,k*w,k*cost);
                nk -= k;
                k *= 2;
            }
            zero_one(n,nk*w,nk*cost);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}


Codeforces 106 C Buns【多重背包】