DP大作战——多重背包

时间：2021-11-04 04:31:08

题目描述

在之前的上机中，零崎已经出过了01背包和完全背包，也介绍了使用-1初始化容量限定背包必须装满这种小技巧，接下来的背包问题相对有些难度，可以说是01背包和完全背包的进阶问题。

多重背包：物品可以有0-n件。

对于第i种物品，我们有取0件，1件…n [ i ] 件共n [ i ] +1种策略，状态转移方程为f [ i ] [ v ] = max { f [ i - 1 ] [ v - k × c [ i ] ] + k × w [ i ] | 0 <=k<= n [ i ] }。在这里，很自然的有一种策略可以将其转化为01背包，即将物品换为n[i]件01背包中的物品，但是复杂度为O(VΣni)，时间复杂度没有降低。实际上，对于所有类似情况，我们都可以利用二进制求和来降低时间复杂度。即将物品替换为价值和费用 * 系数=1,2,2^2,…,2^k,n[i]-2^k+1的物品。系数之和为n [ i ]，表明不能取到多于n [ i ]件物品，但可以取到0…n[ i ]中任意一个整数件。利用这一优化，算法事件复杂度可以降到O(VΣlogni)。

实际上F [ i ] [ j ] 只依赖于 F [ i-1 ] [ j - k * w [ i ] ]，这里依赖项之间构成了一个 { j mod w [ i ] }剩余类，不同剩余类之间无关，注意到这点利用单调队列，每个状态均摊O(1)的时间，可以进一步将算法时间复杂度优化至O(VN)级别的，不过在此不再详细阐述。（其实也就是NOIP程度，放在大学应该可以接受，但是这个优化个人感觉已经脱离dp）

DD大牛给出的伪代码。

def MultiplePack(F,C,W,M)

    if C * M >= V

        CompletePack(F,C,W)

        return //考虑这里为什么可以直接用完全背包

    k := 1

    while k < M

        ZeroOnePack(kC,kW)

        M := M - k

        k := 2k

        ZeroOnePack(C M,W M)

输入

第一个数为数据组数n 1<=n<=10

接下来n组测试数据，每组测试数据由2部分组成。

第一行为背包容量V，物品种类数N。1<=V<=30000,1<=N<=200

接下来N行每行三个数为物品价值v，物品重量w，物品件数M。

1<=v,w<=200, 1<=M<=25

输出

对于每组数据，输出一行，背包能容纳的最大物品价值

输入样例

1

10 2

1 2 3

2 3 2

输出样例

6

题目来源：http://biancheng.love/contest/10/problem/E/index
解题思路：
问题属于背包问题，同时包括了0-1和完全背包，因此为多重背包问题。
按照之前的想法，只要判断每件物品的件数，可以确定对于该物品是使用0-1背包还是完全背包。
0-1背包的代码：
 void Zeronepack(int w,int v)

 {

     for(int i=V; i>=w; i--)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

完全背包的代码：

 void Compack(int w,int v)

 {

     for(int i=w; i<=V; i++)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

本题需要利用0-1背包以及完全背包来解决多重背包问题

代码：

 #include <bits/stdc++.h>

 #include<stdio.h>

 #include<string.h>

 int dp[];

 int V,N;

 void Compack(int w,int v)

 {

     for(int i=w; i<=V; i++)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

 void Zeronepack(int w,int v)

 {

     for(int i=V; i>=w; i--)

         if(dp[i]<dp[i-w]+v)

             dp[i]=dp[i-w]+v;

 }

 int main()

 {

     int kase,v,w,m;

     scanf("%d",&kase);

     while(kase--)

     {

         memset(dp,,sizeof(dp));

         scanf("%d%d",&V,&N);

         for(int i=; i<=N; i++)

         {

             scanf("%d%d%d",&v,&w,&m);

             if(w*m>=V)

                 Compack(w,v);

             else

             {

                 for(int j=; j<m; j<<)

                 {

                     Zeronepack(j*w,j*v);

                     m-=j;

                 }

                 Zeronepack(m*w,m*v);

             }

         }

         printf("%d\n",dp[V]);

     }

     return ;

 }

相关文章