P1060 开心的金明【NOIP2006PJ】

题目内容

P1060

大意:给定 m 件价格分别为 v_i,重要度为 w_i 的物品,求总钱数不超过 N 时最大的 \sum v_iw_i

解题思路

裸的 0-1 背包,直接求解即可,由于这是我写的第一个背包,所以用的是二维数组,也会方便理解一些。

#include <cstdio>

int n,m,v[30],p[30],f[30][30000];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d",&n, &m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&v[i], &p[i]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(v[i]>j)
                f[i][j]=f[i-1][j];
            else
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*p[i]);
        }
    printf("%d\n",f[m][n]);
}

P1048 采药【NOIP2005PJ】

题目内容

P1048

大意:给出若干株草药采摘需要的时间以及他们对应的价值,求在给定时间内能采集到的最大价值,每种草药只有一株

解题思路

还是裸的 0-1 背包,但使用了滚动数组优化空间,注意第二层的循环顺序是从大到小即可。

#include <cstdio>

int f[1005],t,m,w[105],c[105];
inline int max(int x,int y){return x>y?x:y;}

int main()
{
    scanf("%d %d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&w[i],&c[i]);
    for(int i=1;i<=m;i++)
        for(int j=t;j>=w[i];j--)
            f[j]=max(f[j-w[i]]+c[i],f[j]);
    printf("%d\n",f[t]);
    return 0;
}

P1049 装箱问题【NOIP2001PJ]

题目内容

P1049

大意:给定一个容积为 V 的箱子,以及 n 个物品,每个物品有对应的体积,求如何选择能使得剩余空间最小,求剩余空间

解题思路

注意读题:这个是在 n 个物品中选,是 0-1 背包,不是完全背包,一开始我当成完全背包做了半天。

一样的 0-1 背包,只不过在这里所谓的价格和权值相等了都是对应的体积罢了。

#include <cstdio>

int f[20005],v,n,p[35];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d\n%d",&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)
        for(int j=v;j>=p[i];j--)
            f[j]=max(f[j],f[j-p[i]]+p[i]);
    printf("%d\n",v-f[v]);
    return 0;
}

P1616 疯狂的采药

题目内容

P1616

大意:和采药一样,只不过每种草药可以取无限多个

解题思路

看了背包九讲之后,知道了这是一个完全背包问题,解决他我使用了两种方法。

第一种是使用二进制优化,将一个物品拆成费用为 c_i2^k ,价值为 w_i2^k 的物品,其中 k\in{c_i2^k\leq V\mid k\in\N}。这样就成功将处理一个物品变为处理 O(\log\frac V{c_i}) 个物品,这样就可以使用 0-1 背包解决问题了。

#include <cstdio>

int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d", &t ,&m);
    totm=1;
    for(int i=1;i<=m;i++)
    {
        int ww, cc;
        scanf("%d %d", &cc, &ww);//cc is time, ww is value
        for(int j=0;(1<<j)*cc<=t;j++)//读入的时候就要进行处理
        {
            w[totm]=ww*(1<<j);//位运算可香了
            c[totm++]=cc*(1<<j);
        }
    }
    for(int i=1;i<=totm;i++)//然后就是和 0-1 背包一模一样的处理
        for(int j=t;j>=c[i];j--)
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d\n",f[t]);
    return 0;
}

第二种就是常规的完全背包,就是将 0-1 背包的内层循环改了顺序而已,代码如下:

#include <cstdio>

int t,m,f[100010],totm,w[100010],c[100010];
inline int max(int a,int b){return a>b?a:b;}

int main()
{
    scanf("%d %d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&c[i],&w[i]);
    for(int i=1;i<=m;i++)
        for(int j=c[i];j<=t;j++)//注意这里的顺序
            f[j]=max(f[j],f[j-c[i]]+w[i]);
    printf("%d\n",f[t]);
    return 0;
}
最后修改日期:2020年2月19日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。