美文网首页
《背包九讲》笔记

《背包九讲》笔记

作者: 染微言 | 来源:发表于2017-03-29 17:18 被阅读560次

    背包问题

    题意:给出背包的容量,以及一批物品的价值和大小,求最大价值。

    01背包问题

    题意

    每个物品只能放入一次。

    思路

    f[i][v]表示,第i个大小为v的物品放入时的总价值。
    c[i]表示第i个物品的价值。w[i]为第i个物品的大小。
    状态转移方程:f[i][v] = max(f[i-1][v], f[i-1][v-w[i]]+c[i]);
    状态转移方程表示,取放入或者不放入第i个物品两种情况的最大值。

    空间优化(滚动数组)

    初始状态方程的空间复杂度是O(V*W),可以进一步优化。
    可以将空间优化为O(2*W),即纵向大小为2。

    for(i=1; i<=N; i++){
      for(j=t[i]; j<=V; j++)
        f[t^1][j] = max(f[c][j-w[i]]+c[i], f[t][j]);
      t ^= 1;
    }
    

    异或滚动可以在0和1之间切换,可以利用上下反复更新。

    空间优化(一维数组)

    既然可以用两行进行更新,那为什么不能用一行。
    观察问题,两行更新时,用上一行的前部分更新下一行的后部分。
    所以单行更新时要从后往前遍历,这样可以用前面的更新后面的。

    for(i=1; i<=N; i++)
      for(j=V; j>=w[i]; j--)
        f[j] = max(f[j-w[i]]+c[i], f[j]);
    

    这样就可以用一维数组来进行更新。
    可以写成函数,封装起来。

    void ZeroOnePack(int cost, int weight){
        for(int i=V; i>=weight; i++)
            f[i] = max(f[i], f[i-weight]+cost)
    }
    

    初始化的细节问题

    一般问题会有两种问法:

    1. 刚好装满背包
    2. 不用装满背包
      如果是第一种,f[0]=0,f[1]……f[N]=INF;
      如果是第二种,f[0]……f[N]=INF;
      理解:
      如果是第一种,初始状态只有0符合理想状态,只有0才能被空“装满”。
      如果是第二种,所有都符合理想状态。

    完全背包问题

    题意

    和01背包相似,所不同的是可取的物品数是无限。

    前置小优化

    对于i``j两个物品,如果c[i]>c[j] && w[i]<w[j],就舍去i物品。
    另外,针对背包问题而言,比较不错的一种方法是:首先将重量大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。

    基本思路

    状态转移方程f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]},(0<=k*w[i]<=V)

    转化为01背包求解

    一件物品最多只能放V/c[i]件,所以可以把一件物品,看成V/c[i]件物品,作为01背包解答。
    另一种更好的办法是把第i种物品拆成大小为w[i]*2^k、价值为c[i]*2^k的若干件物品,其中k满足w[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/w[i]))件物品,是一个很大的改进。

    O(VN)算法

    for(int i=1; i<=N; i++)
        for(int j=w[i]; j<=V; j++)
            f[j] = max{f[v], f[v-w[i]]+c[i]};
    

    这个算法和之前的01背包相比只是第二层的遍历方向改变了。因为01背包要保证每个物品只能选择一次,但是完全背包不必,所以改变遍历方向就可以得到结果。
    这个算法也可以从另外的思路中得出,例如,基本思路中的公式可以化作这个形式:f[i][v]=max(f[i-1][v], f[i][v-w[i]]+c[i]);
    用函数封装:

    void CompletePack(int cost, int weight){
        for(int i=weight; i<=V; i++)
            f[i] = max(f[i], f[i-weight]+cost);
    }
    

    多重背包问题

    题意

    每件物品数量不一定为1但有限。

    基本思路

    问题和完全背包很相似。
    f[i][v]=max{f[i-1][v-k*c[i]]+k*w[I]}(0<=k<=n[I])
    复杂度为O(V*Σn[i])

    转化为01背包问题

    n[i]存储,可以将每种物品转化为n[i]件物品,然后用01背包方案求解。复杂度不变。
    如果要进行优化的话,依然用二进制思想,同上。
    这样可以将时间优化为O(V*Σlog n[i])

    void MultiplePack(int weight, int cost, int amount){
        if(cost * amount >= V){
            CompletePack(cost, weight);
            return;
        }
        int k = 1;
        while(k < num){// num 为物品种数
            ZeroOnePack(k*cost, k*weight);
            amount = amount-k;
            k *= 2;
        }
        ZeroOnePack(amount*cost, amount*weight);
    }
    

    相关文章

      网友评论

          本文标题:《背包九讲》笔记

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