前言：

其实在最开始接触贪心的时候就知道这种背包问题了，然后我就死想贪心思路，但是根本想不到好吧，然后觉得这种背包问题真的是好厉害，世界上一定没有什么方法来解决背包问题了吧，但是只从我开始学了DP之后就明白了，原来这么简单QAQ

背包问题模板：

0/1背包问题

方法：

倒着逐步选择更新

代码：

1
2
3
4
5
6
for(int i=1;i<=Things;i++)
{
    cin>>Weight>>Value;
    for(int j=Bag_weight;j>=Weight;j--)
    f[j]=max(f[j],f[j-Weight]+Value[i]);
}

完全背包问题

方法：

0/1背包的基础上进行正序更新

代码：

1
2
3
4
5
6
for(int i=1;i<=Things;i++)
{
    cin>>Weight>>Value;
    for(int j=Weight;j<=Bag_weight;j++)//循环方式和0/1是反的
    f[j]=max(f[j],f[j-Weight]+Value[i]);
}

多重背包问题

方法：

有数量限制，如果相当于无限多，那么就按照完全背包的处理方法，如果有限，转换为取1—n个的物品，用0/1背包加二进制优化。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=1;i<=n;i++)
{
    if(a[i].Weight*a[i].Number>Bag_weight)//如果可以用完全背包
    {
        for(int j=a[i].Weight;j<=Bag_weight;j++)
        f[j]=max(f[j],f[j-a[i].Weight]+a[i].Value);
    }
    else
    {
        int This_number=1,Surplus=a[i].Number;//Surplus指的是要将物品几个分成一组
        while(This_number<Surplus)
        {
            for(int j=Bag_weight;j>=a[i].Weight*This_number;j--)
            f[j]=max(f[j],f[j-a[i].Weight*This_number]+a[i].Value*This_number);
            Surplus-=This_number;//This_number存储还剩下几个物品没有成一组
            This_number+=This_number;//再次分成一组
        }
        for(int j=Bag_weight;j>=a[i].Weight*Surplus;j--)//0/1背包
        f[j]=max(f[j],f[j-a[i].Weight*Surplus]+a[i].Value*Surplus);
    }
}

混合背包问题

方法：

混合背包判断是0/1背包就0/1背包处理，是完全背包就完全背包处理，是非一个非无穷的就按照多重背包处理。

代码：

代码和楼上一样，不粘了。

二维费用流背包问题

方法：

增加要处理的维度，然后和前面的处理是一样的；

代码：

1
2
3
4
for(int i=1;i<=n;i++)
for(int j=The_Need_N2*3;j>=a[i].There_N2;j--)
for(int k=The_Need_O2*3;k>=a[i].There_O2;k--)
f[j][k]=min(f[j][k],f[j-a[i].There_N2][k-a[i].There_O2]+a[i].Weight);

分组背包问题

方法：

比如下面的分组有两组，两组是有冲突的每次只能选择其中的一组，我们只要放在一起直接当时处理掉，这样到后面不会有两个都有选择的情况。

代码：

1
2
3
4
5
6
for(int i=1;i<=n;i++)
for(int j=Time;j>=min(a[i].Right_time,a[i].Wrong_time);j--)
{
    if(j>=a[i].Right_time) f[j]=max(f[j],f[j-a[i].Right_time]+a[i].Right_point);
    if(j>=a[i].Wrong_time) f[j]=max(f[j],f[j-a[i].Wrong_time]+a[i].Wrong_point);
}

特殊要求

字典序最小方案

解法：

方案总数: f[j]=f[j]+f[j-Weight];

最优方案

解法：

最优方案的总数：在计算f[i][j]的同时，记录下来一个g[i][j]，如果和当前最大值相等，就加上到达当前最大值的方案数。

代码：

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)
{
    g[i][j]=0;
    if(f[i][j]==f[i-1][j])
    g[i][j]+=g[i-1][j];
    if(f[i][j]==f[i-1][j-Weight]+Value)
    g[i][j]+=g[i-1][j-Weight];
}

第K优解

方法：

建立一个数组f[i][j][k]，其中k表示第k优解，然后另外新建两个数组（其实可以建立一个，但是需要排序，比较耗费时间），然后记录下来选择f[i-1][j][k]，和f[i-1][j-weight][k]+value的值的时候，分别的值，然后最后进行同时合并。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i=1;i<=n;i++)
{
    cin>>Weight>>Value;
    for(int j=v;j>=Weight;j--)
    {
        for(int k=1;k<=Person;k++)//两个数组记录方案
        {
            First[k]=f[j][k];
            Second[k]=f[j-Weight][k]+Value;
        }
        First[Person+1]=Second[Person+1]=-1;
        int This=1,The_First=1,The_Second=1;
        while(This<=Person)//最后根据大小分配到k优解中
        {
            if(First[The_First]>Second[The_Second])
            f[j][This]=First[The_First++];
            else f[j][This]=Second[The_Second++];
            This++;
        }
    }
}

背包问题的搜索算法

方法：

能不去搜索尽量不要搜，不然会后悔的……超级麻烦！(下面附上P1280的代码)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void DFS(int Now_Thing,int Now_CD,int Now_times,int ans)
{
    if(Get[Now_Thing][Now_CD][Now_times][ans]==true) return;
    else Get[Now_Thing][Now_CD][Now_times][ans]=true;
    if(Time<a[Now_Thing])
    {
        DFS(Now_Thing+1,Now_CD,Now_times,ans);
        return;
    }
    if(Now_CD>CD)
    {
        The_max=max(The_max,ans-1);
        return;
    }
    if(Now_Thing>n)
    {
        The_max=max(The_max,ans);
        return;
    }
    The_max=max(The_max,ans);
    if(Now_times+a[Now_Thing]<=Time)
    DFS(Now_Thing+1,Now_CD,Now_times+a[Now_Thing],ans+1);
    else DFS(Now_Thing+1,Now_CD+1,a[Now_Thing],ans+1);
    DFS(Now_Thing+1,Now_CD,Now_times,ans);
}

背包问题完结

背包问题总算是AC完了，这几天效率很高，很充实，加油吧！