背包问题-01背包，完全背包，多重背包-蒲公英云

背包问题-01背包，完全背包，多重背包

01背包：

概念：

有Goods_Num件物品，MAX_Volume的最大装载量，每种物品只有一件，每种物品都有对应的重量或者说体积Volume[i]，价值Value[i]，求解装包的最大价值

状态转移方程推导：

假设目前已经有 i-1件物品装在容量为 j 的背包中，并且得到最大价值Package[ i-1 ][ j ]，当前装第i件，那么讨论分两个角度，如果第i个物品装不入背包，那么最大价值不变。如果第i个物品可以放入，那么如果背包容量为 j-Volume[i]的时候的最大装包价值加上第i个物品价值大于Package[i-1][j]，那么Package[i][j]最大价值就更新了，否则就不装i

得到状态转移方程：

a. Volume[ i ] > j ：Package[ i-1 ][ j ]

b. j >= Volume[ i ] ：max( Package[ i-1 ][ j-Volume[i] ] +Value[ i ], Package[ i-1 ][ j ] )

实现代码：

#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
#define MAX_SIZE 1024
int Volume[MAX_SIZE];    /*每个物品所占空间（或重量）*/
int Value[MAX_SIZE];     /*物品价值*/
int Package[MAX_SIZE][MAX_SIZE];   /*未优化，Package[i][j] 表示前i个物品放入容量为j的购物车的最大价值*/
int MAX_Volume, Goods_Num;  /*最大容量，物品数量*/
void Init()
{
    memset(Package, 0, sizeof(Package));
}
void _01Package()
{
    for (int i = 1; i <= Goods_Num; i++)
    {
        for (int j = 1; j <= MAX_Volume; j++)
        {
            if (j < Volume[i])     /*装不下第i个物品*/
                Package[i][j] = Package[i - 1][j];
            else
                Package[i][j] = max(Package[i - 1][j], Package[i - 1][j - Volume[i]] + Value[i]);
                /*将第i个物品放在容量为j - Volume[i]（已得的最优情况）的购物车里*/
        }
    }
}
void Print_Res()  /*打印结果*/
{
    cout << "The max value of Package:" << Package[Goods_Num][MAX_Volume] << endl;
    int i, j = MAX_Volume;
    cout << "Goods in Package: ";
    for (int i = Goods_Num; i > 0; i--)
    {
        if (Package[i][j] > Package[i - 1][j])
        {
            cout << i<<" ";
            j -= Volume[i];
        }
    }
    cout << endl;
}

优化：

在设计算法时会发现，上一层的数据在本层中并没有修改，而是作为状态的记录，而且本层当前Index只会用到上一层Index之前的数据，所以可以降成一维，称为滚动数组。并且要求每次都重后往前遍历，避免重复叠包

优化代码：

#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
#define MAX_SIZE 1024
int Volume[MAX_SIZE];    /*每个物品所占空间（或重量）*/
int Value[MAX_SIZE];     /*物品价值*/
int _Package[MAX_SIZE];   /*优化后,Package[i]表示容量i的购物车所获得的最大价值*/
int MAX_Volume, Goods_Num;  /*最大容量，物品数量*/
void Init()
{
    memset(_Package, 0, sizeof(_Package));
}
void _01Package_Optimize()  /*优化算法*/
{
    for (int i = 1; i <= Goods_Num; i++)
        for (int j = MAX_Volume; j >= Volume[i]; j--) /*每个物品最多只能装一次，从后开始遍历防止最优情况叠加*/
            _Package[j] = max(_Package[j], _Package[j - Volume[i]] + Value[i]);
}
void Print_Res_Optimize()
{
    cout << "The max value of Package:" << _Package[MAX_Volume] << endl;
}

完全背包：

概念：

有Goods_Num件物品，MAX_Volume的最大装载量，每种物品数量无限，每种物品都有对应的重量或者说体积Volume[i]，价值Value[i]，求解装包的最大价值

状态转移方程推导：

与01背包的思路基本相似，不过重要的一点是，每种物品是无限的，所以背包可以多填

得状态转移方程：

a. Volume[ i ] > j ：Package[i-1][ j ]

b. j>=Volume[ i ] ：max( Package[ i-1 ][ j-m\Volume[ i ] ] +m*Value[ i ], Package[ i-1 ][ j ] )*

实现代码：

#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
#define MAX_SIZE 1024
int Volume[MAX_SIZE];    /*每个物品所占空间（或重量）*/
int Value[MAX_SIZE];     /*物品价值*/
int Package[MAX_SIZE][MAX_SIZE];   /*未优化，Package[i][j] 表示前i个物品放入容量为j的购物车的最大价值*/
int MAX_Volume, Goods_Num;  /*最大容量，物品数量*/
void Init()
{
    memset(Package, 0, sizeof(Package));
}
void Total_Package()
{
    for (int i = 1; i <= Goods_Num; i++)
    {
        for (int j = MAX_Volume; j >= Volume[i]; j--)  /*重后往前避免单物品多填影响后序的填包，后填不影响前*/
        {
            int k = j / Volume[i];   /*最多再填k个i物品*/
            for (int m = 0; m <= k; m++)
                Package[i][j] = max(Package[i - 1][j - m * Volume[i]] + m * Value[i], Package[i - 1][j]);
        }
    }
}

优化代码：

#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
#define MAX_SIZE 1024
int Volume[MAX_SIZE];    /*每个物品所占空间（或重量）*/
int Value[MAX_SIZE];     /*物品价值*/
int _Package[MAX_SIZE];   /*优化后,Package[i]表示容量i的购物车所获得的最大价值*/
int MAX_Volume, Goods_Num;  /*最大容量，物品数量*/
void Init()
{
    memset(_Package, 0, sizeof(_Package));
}
void Total_Package_Optimize()  /*优化算法*/
{
    for (int i = 1; i <= Goods_Num; i++)
    {
        for (int j = Volume[i]; j <= MAX_Volume; j++)/*一维，从前往后dp才能实现一个物品的多填*/
            _Package[j] = max(_Package[j], _Package[j - Volume[i]] + Value[i]);
    }
}
void Print_Res_Optimize()/*打印*/
{
    cout << "The max value of Package:" << _Package[MAX_Volume] << endl;
}

多重背包：

概念：

有Goods_Num件物品，MAX_Volume的最大装载量，第i件物品有数量为Num[i]，每种物品都有对应的重量或者说体积Volume[i]，价值Value[i]，求解装包的最大价值

状态转移方程推导：

其实就是在一个展开的01背包问题，比如有3件相同物品，不如将它展开成 1 1 1 形式，然后01装包

状态转移方程：

a. Volume[ i ] > j ：Package[ i-1 ][ j ]

b. j >= Volume[i] ：max( Package[ i-1 ][ j-Volume[ i ] ] +Value[i], Package[ i-1 ][ j ] )

只不过，对于物品数大于1的，需要展开Num[i]次

实现代码：

#include<iostream>
#include<algorithm>
#include<memory>
using namespace std;
#define MAX_SIZE 1024
int Volume[MAX_SIZE];    /*每个物品所占空间（或重量）*/
int Value[MAX_SIZE];     /*物品价值*/
int Num[MAX_SIZE];    /*i物品的个数*/
int Package[MAX_SIZE];   /*优化后,Package[i]表示容量i的购物车所获得的最大价值*/
int MAX_Volume, Goods_Num;  /*最大容量，物品数量*/
void Init()
{
    memset(Package, 0, sizeof(Package));
}
void Multi_Package()
{
    for (int i = 1; i <= Goods_Num; i++)
    {
        for (int j = 1; j <= Num[i]; j++)
        {
            for (int k = MAX_Volume; k >= Volume[i]; k--)
                Package[k] = max(Package[k], Package[k - Volume[i]] + Value[i]);
        }
    }
}
void Print_Res()
{
    cout << "The max value of Package:" << Package[MAX_Volume] << endl;
}

优化：

这时候想一个问题，如果一件物品的数量很大很大，那么，对于第三个循环需要跑的时间就很长，在前面说过，多重背包是可拆成01背包形式，那么，何不提前处理 Volume[MAX_SIZE]，Value[MAX_SIZE]，将问题先转成01背包。

转化时有技巧，运用快速幂的知识，将一件物品拆成 1，2，4…….，当然有个容易想的前提：1~N的数可由2的若干指数和表示

优化代码：

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
#define MAX_SIZE 1024
int Op_Vol[MAX_SIZE];   /*优化后的物品体积*/
int Op_Val[MAX_SIZE];   /*优化后的物品价值*/
int Package[MAX_SIZE];   /*背包*/
int MAX_Volume,GoodsNum;  /*背包最大体积，原先的货品数量*/
int Op_GoodsNum;   /*优化后的物品数*/
void Init()  /*初始化*/
{
    Op_GoodsNum=0;
    memset(Op_Val,0,sizeof(Op_Val));
    memset(Op_Vol,0,sizeof(Op_Vol));
    memset(Package,0,sizeof(Package));
}
void Multi_Package()
{
    for(int i=1;i<=Op_GoodsNum;i++)   /*优化后转变为01背包问题*/
    {
        for(int j=MAX_Volume;j>=Op_Vol[j];j--)
            Package[j]=max(Package[j],Package[j-Op_Vol[i]]+Op_Val[i]);
    }
}
int main()
{
    int vol,val,num;
    while(cin>>GoodsNum>>MAX_Volume)
    {
        Init();
        for(int i=1;i<=GoodsNum;i++)
        {
            cin>>vol>>val>>num;
            for(int j=1;j<=num;j<<=1)   /*优化成01背包问题*/
            {
                Op_Val[++Op_GoodsNum]=j*val;
                Op_Vol[Op_GoodsNum]=j*vol;
                num-=j;
            }
            if(num>0)
            {
                Op_Val[++Op_GoodsNum]=num*val;
                Op_Vol[++Op_GoodsNum]=num*vol;
            }
        }
        Multi_Package();
        cout<<Package[MAX_Volume]<<endl;
    }
    return 0;
}