01背包模板

作者: 1QzUPm_09F | 来源:发表于2017-02-18 00:47 被阅读0次

    01背包问题:
    有N件物品和一个容量为v的背包。第i件物品的体积(质量)是volume[i],价值是value[i]。求解将哪些物品装入背包可使价值总和(dp[ ])最大。

    01背包的特点就是:每种物品仅有一件,可以选择放或不放。

    核心代码:dp[i][v]=max(dp[i-1][v],dp[i-1][v-c[i]]+w[i])

    理解:现在需要放置的是第i件物品,这件物品的体积(质量)是c[i],价值是w[i],
    因此f[i-1][v]代表的就是不将这件物品放入背包,
    f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值,
    比较两者的价值,得出最大的价值存入现在的背包之中。

    模板例题:

    [HDU - 2602](https://vjudge.net/problem/17434/origin)

    代码:

    #include<algorithm>
    #include<string.h>
    #include<stdio.h>
    using namespace std;
    int dp[1005], volume[1010], value[1010];
    int main()
    {
        int i, j, n, v, k;
        scanf("%d", &k);
        while(k--)
        {
            memset(dp,0,sizeof(dp));
            memset(value,0,sizeof(value));
            memset(volume,0,sizeof(volume));
            scanf("%d%d", &n, &v);
            for(i=1; i<=n; i++)
            {
                scanf("%d", &value[i]);
            }
            for(i=1; i<=n; i++)
            {
                scanf("%d", &volume[i]);
            }
    
            for(i=1; i<=n; i++)
            {
                for(j=v; j>=volume[i]; j--)
                {
                    if(dp[j]<dp[j-volume[i]]+value[i])
                    {
                        dp[j]=dp[j-volume[i]]+value[i];
                    }
                }
            }
            printf("%d\n", dp[v]);
        }
        return 0;
    }
    

    模板:

            for(i=1; i<=n; i++)
            {
                for(j=v; j>=volume[i]; j--)
                {
                    if(dp[j]<dp[j-volume[i]]+value[i])
                    {
                        dp[j]=dp[j-volume[i]]+value[i];
                    }
                }
            }
    

    01背包路径查找模板题


    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    using namespace std;
    struct node
    {
        int volume, value;
        int id;
    } v[10010];
    int dp[10010], pre[100][10010];
    int res[10010];
    int main()
    {
    
        int cnt=1;
        int T;
        scanf("%d", &T);
        while(T--)
        {
            int n, m;
            scanf("%d%d", &n, &m);
    
            memset(pre,0,sizeof(pre));
            memset(dp,0,sizeof(dp));
            memset(v,0,sizeof(v));
            memset(res,0,sizeof(res));
    
            for(int i=1; i<=m; i++)
            {
                scanf("%d%d", &v[i].value, &v[i].volume);
                v[i].id=i;
            }
    
            for(int i=1; i<=m; i++)
                for(int j=n; j>=v[i].volume; j--)
                    if (dp[j-v[i].volume]+v[i].value > dp[j])
                    {
                        dp[j]=dp[j-v[i].volume]+v[i].value;
                        pre[i][j]=1;
                    }
    
            int sum1=0, sum2=0, k=0;
            for(int i=m,j=n; i>0; i--)
            {
                if(pre[i][j]==1)
                {
                    sum1+=v[i].value;
                    sum2+=v[i].volume;
                    res[k++]=v[i].id;
                    j-=v[i].volume;
                }
            }
    
            printf("Case #%d:\n", cnt++);
            printf("%d %d\n", sum1, sum2);
    
            sort(res, res+k);
            for(int i=0; i<k; i++)
            {
                if(i!=0) printf(" ");
                printf("%d", res[i]);
                if(i==k-1) printf("\n");
            }
        }
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:01背包模板

        本文链接:https://www.haomeiwen.com/subject/bklrwttx.html