动态规划-背包问题

~~你看这个背包它不香吗？~~

背包问题是动态规划（DP）问题中的一类，大致分为01背包，完全背包，分组背包以及混合背包。当然，通过这几类背包问题~~加上毒瘤的出题人~~也衍生出了一大批其他的背包问题，如有依赖的背包问题。问题的主旨是通过选取部分物品使得在有限的背包容量下得到最大的物品价值。

首先是01背包问题。

描述

一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。

输入

第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；

第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

输入样例 1

输出样例 1

顾名思义，它对于每一件物品，都只有0和1两种状态即选取或者不选取。也就是说，我们需要在n件物品中选取一部分，让它们能够在容量为(v)的背包里装得下且得到的价值最大。

所以考虑每一件物品在选或者不选的情况下对于最终情况的影响。不难发现，一件物品的加入，同时代表着总价值的增加以及背包剩余容量的减少，所以每次加入新的物品/替换旧的物品都可以视作一种决策。这种决策需要在比之前的决策更优的时候再作出。

分别用(v[i])和(w[i])表示第i件物品的重量和价值。为了保证每件物品只选用一种，我们要保证在dp过程中，后得到的答案不影响先得到的答案，所以很明显dp的内层循环应该是从m往下循环，这样得出的结果才会不受其前面答案的影响。

考虑用(dp[i])表示容量为(i)的背包能够装下的最大价值。同时为了决策的较优性，我们要保证每次用来替换的这个(w[i])大于当前的容量(j)（否则无法完成替换）。

CODE:

#include<bits/stdc++.h>
using namespace std;
int v[1010],w[1010],dp[1010],n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)
		for(int j=m;j>=w[i];j--)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	cout<<dp[m]<<endl;
	return 0;
}

完全背包问题:

在01背包的基础上去掉了每种物品只有一件的限制，改成了每种物品可以有无数件。

也就是说，在dp的过程中，即使后来的答案影响了前面得出的dp值，也不会有任何影响。

所以只需要把01背包模板中控制这一板块的循环顺序给修改了就是完全背包的模板了。惊不惊喜？意不意外？

CODE:

#include<bits/stdc++.h>
using namespace std;
int v[1010],w[1010],dp[1010],n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i];
	for(int i=1;i<=n;i++)
		for(int j=w[i];j<=m;j++)
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	cout<<dp[m]<<endl;
	return 0;
}

多重背包问题

多重背包也是在01背包的基础上添加了一个限制条件，即每种物品有(k)件（由输入给出）。

我们可以通过01背包来处理有一件物品的情况，那有(k)件呢？

没错，循环(k)次！（？？？）

在01背包模板中的两层循环中间，加上一个循环(k)次的(for)就可以了。

CODE

#include<bits/stdc++.h>
using namespace std;
int v[1010],w[1010],dp[1010],p[1010],n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>w[i]>>v[i]>>p[i];
	for(int i=1;i<=n;i++)
        for(int k=1;k<=p[i];k++)
            for(int j=m;j>=w[i];j--)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	cout<<dp[m]<<endl;
	return 0;
}

混合背包问题：

再次顾名思义，混合背包就真的只是把01，完全，多重给融合了起来，每种物品可以有一件，无数件以及多重背包的有(k)件

因为它是混合起来的背包问题，所以我们也把代码给混合起来吧！（？？？）

没错，我们可以把01背包视作特殊的多重背包来处理，那么这三种背包问题就可以用(if-else)分为两类，然后分别处理就可以了。

CODE

#include<bits/stdc++.h>
#define max(a,b) a>b?a:b
using namespace std;
int m,n;
int w[1001],v[1001],p[1001],dp[2001];
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i]>>p[i];
    for(int i=1;i<=n;i++)
        if(p[i]==0)
            for(int j=w[i];j<=m;j++)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        else
            for(int j=1;j<=p[i];j++)
                for(int k=m;k>=w[i];k--)
                    dp[k]=max(dp[k],dp[k-w[i]]+v[i]);
    cout<<dp[m]<<endl;
    return 0;
}

ov.后期持续更新