【背包问题】0-1背包、完全背包、多重背包、混合三种背包、二位费用背包、分组背包

一、0-1背包问题

输入：第一行物品的个数n，第二行背包的质量m，随后n行每行给出每个物品的重量和价值，每种物品只有一个。

输出：背包可以达到的最大价值

样例输入：

5 10

1 5

2 4

3 3

4 2

5 1

样例输出：

动态规划的过程中需要逆序，因为如果不是逆序那么

当i=0的时候

f[0]=0;

f[1]=max(f[1],f[1-w[0]]+v[0])=5;

f[2]=max(f[2],f[2-w[0]]+v[0])=10;

f[3]=max(f[3],f[3-w[0]]+v[0])=15;

….

f[10]=max(f[10],f[10-w[0]]+v[0])=50

显然不对，因为每种物品只有一个，而顺序遍历可能会用到第i件物品在前一种状态已经放入的情况

#include <iostream>
#include <cstring>

using namespace std;
int n,m,f[1111],w[1111],v[1111];
//m背包的总容量、v物品的体积、w物品的价值
void OneZeroPack(int m,int v,int w)  //0-1背包
{
    for(int i=m;i>=v;i--)
        f[i]=max(f[i],f[i-v]+w);
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
            cin>>v[i]>>w[i];
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++)
            OneZeroPack(m,v[i],w[i]);
        cout<<f[m]<<endl;
    }
    return 0;
}

如果需要全部装满，那么初始化数组的时候，只把f[0]=0其余的赋值-∞

二、完全背包问题

输入：第一行物品的个数n，第二行背包的质量m，随后n行每行给出每个物品的重量和价值，每种物品有无限多个。

输出：背包可以达到的最大价值

样例输入：

5 10

1 5

2 4

3 3

4 2

5 1

样例输出：

如果每种无限多个那就应该是顺序遍历，上面解释过。。。

代码：只在上面那个基础上改这一点就行

for(int i=0;i<n;i++)
for(int j=w[i];j<=m;j++)
        f[j]=max(f[j],f[j-w[i]]+v[i]);

三、多重背包

和完全背包很相似，对于每件物品有num[i]+1中策略:0件，1件，2件…num[i]件,则有状态转移方程：f[i][v] = max{F[i−1][v−k∗Ci] + k∗Wi |0 ≤ k ≤ Mi}

复杂度是O(V ΣMi)

　　二进制优化时间复杂度O(VNlogM)

可以转化为0-1背包问题直接求解，复杂度仍然是O(V ΣMi)。但是我们可以通过二进制的思想进行优化降低时间复杂度。将第i种物品分成若干件物品，此中每件物品有一个系数，这件物品的费用和价值均是本来的费用和价值乘以这个系数。使这些系数分别为 1，2，4，...，2^（k-1），n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，若是n[i]为13，就将这种物品分成系数分别为1，2，4，6的四件物品。

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2844

解题报告：http://www.cnblogs.com/asuml/p/5730400.html

四、混合三种背包

很好理解直接附上伪代码：

for i=0 to n-1

if i为0-1背包

OneZeroPack(int m,int v,int w)

Else if i为完全背包

CompletePack(int m,int v,int w)

Else

MultiplePack(int m,int v,int w,int num)

五、二维费用的背包

费用加了一维状态对应的增加一维即可

三维转移方程：F[i,v,u] = max{F[i−1,v,u],F[i−1,v−Ci,u−Di] + Wi}

二维转移方程：F[v,u]=max{F[v,u],F[v−Ci,u−Di] + Wi}

六、分组的背包问题

1．问题

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

2.转移方程：

F[k,v] = max{F[k−1,v],F[k−1,v−Ci] + Wi |item i ∈ group k}

3.伪代码：

For k=1 to K

For v=V to 0

For 所有的i属于组k

F[v]=max{f[v],f[v-c[i]]+a[i]

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1712

解题报告：http://www.cnblogs.com/asuml/p/5732073.html

【背包问题】0-1背包、完全背包、多重背包、混合三种背包、二位费用背包、分组背包

推荐阅读