精华内容
下载资源
问答
  • 分组背包

    2017-10-28 19:57:25
    分组背包

    转自:分组背包
    问题    
    有N件物品和一个容量为V的背包。第i件物品的费用是w[i],价值是c[i]。

    这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    算法   

    这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。

    也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,

    则有f[k][v]=max{f[k-1][v],f[k-1][v-w[i]]+c[i]|物品i属于第k组}。

    使用一维数组的伪代码如下:

    for 所有的组k for v=V..0

    for 所有的i属于组k       

    f[v]=max{f[v],f[v-w[i]]+c[i]}   
    注意这里的三层循环的顺序,
    “for v=V..0”这一层循环必须在“for 所有的i属于组k”之外
    。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
    另外,显然可以对每组中的物品应用完全背包中“一个简单有效的优化”。
    【问题描述】
    一个旅行者有一个最多能用V公斤的背包,现在有n件物品,它们的重量分别是W1,W2,…,Wn,它们的价值分别为C1,C2,…,Cn。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
    【输入格式】
    第一行:三个整数,V(背包容量,V<=200),N(物品数量,N<=30)和T(最大组号,T<=10);
    第2..N+1行:每行三个整数Wi,Ci,P,表示每个物品的重量,价值,所属组号。
    【输出格式】
    仅一行,一个数,表示最大总价值。
    【样例输入】group.in
    10 6 3
    2 1 1
    3 3 1
    4 8 2
    6 9 2
    2 8 3
    3 9 3
    【样例输出】group.out
    20
    参考程序

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    int v,n,t,p;
    int w[31],c[31];
    int f[201],a[11][32];
    int main(){
    scanf("%d%d%d",&v,&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&w[i],&c[i],&p);
        a[p][++a[p][0]]=i;
       }
    for(int k=1;k<=t;k++)
       for(int j=v;j>=0;j--)
         for(int i=1;i<=a[k][0];i++)
           if(j>=w[a[k][i]]){
              int tmp=a[k][i];
              if(f[j]<f[j-w[tmp]]+c[tmp])
                f[j]=f[j-w[tmp]]+c[tmp];
     }
    printf("%d",f[v]);
    return 0;
    }
    展开全文
  • 分组 背包

    2013-03-27 21:15:13
    分组背包 一、分组背包 背包九讲上这样说的 有N件物品和一个容量为V的的背包,第i件物品的费用为C[i],价值是w[i]。这些物品被划分为若干组,每组的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品...

    分组背包

    一、分组背包

    背包九讲上这样说的

    有N件物品和一个容量为V的的背包,第i件物品的费用为C[i],价值是w[i]。这些物品被划分为若干组,每组的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过物品的容量,且价值最大。

    大牛给出的状态转移方程为:

    f[k][v]=max(f[k-1][v],f[k-1][v-c[i]]+w[i])

    伪代码

    (1)for 所有的组k

    (2)do for v<-V to 0

    (3)do for 所有的i属于组k

          f[v]=max(f[v],f[v-c[i]]+w[i]);

    大牛还特别强调,(2)(3)为了保证保证每一组最多只有一个会装进背包里,二者不能够调换。我是这样理解的,二者交换后,(2)(3)构成的将是01背包,01背包不限制个数的,所以交换后就不能保证,装的最多一个了。

    不交换的,更像是一种枚举去找最佳状态,所以我对大牛只有膜拜。

    二、这次做题的时候遇见了,一种背包,是这样描述的

    有N件物品和一个容量为V的的背包,第i件物品的费用为C[i],价值是w[i]。这些物品被划分为若干组,每组的物品互相冲突,最少选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过物品的容量,且价值最大。

    好让人迷茫呀,想了半天没一点进步,只好去搜博客,幸好搜到一个大牛的代码。http://www.cnblogs.com/ACMan/archive/2012/08/13/2637022.html

    他给出的状态转移方程是dp[i][j]=max(dp[i][j],max(dp[i-1][j-c[i]]+w[i],dp[i][j-c[i]]+w[i]));

    dp[i][j]表示不选择当前工作

    dp[i-1][j-c[x]]+w[i]表示第一次在本组中选物品

    d[i][j-c[i]]+w[i]表示当前物品不是第一次取

    由于选取的物品,不再局限于一个所以

    (1)for 所有的组k

    (3)do for 所有的i属于组k

    (2)do for v<-V to 0

          f[v]=max(f[v],f[v-c[i]]+w[i]);

    一定又问了,怎样保证选取的至少是一个,那么就在初始化让所有dp[i][0---V]都为负无穷,杭电3535是道不错的题,它是这两种背包结合再加上01背包,

    这一题代码,大牛哪给的很详细,我就不献丑了。

    当然,也要注意数组的初始化

    题外话:做这道题的时候我想要放弃了,我认为他很难,他让我差点怀疑自己的实力,很是打击我,而现在,我发现自己确实很弱,不是知识的弱,而是学习态度,总是一知半解就满足了,如果我把背包九讲上的分组背包,理解透了,01背包理解透了,这道题就不会那样让我感到压抑,让我差点放弃。

    态度决定一个人的生活方式,决定对世界的认识。



    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,953
精华内容 1,181
关键字:

分组背包