01背包前k优解方案

[刷题记录]洛谷P1858 多人背包

题目链接：P1858多人背包

题意解释

  • 传统的01背包问题：有一堆物品和一个固定容量的背包，每个物品有自己的体积和价值，要求求出能装入背包的所有物品对应的最大总价值；

  • 这道题又多出了一个k值，表示有k个背包，意思是要求你求出上述问题的前k优解的总和；

  • 当然，题目里还有一个要注意的地方就是：要求背包恰好装满，因此需要在初始化的时候做点手脚就可以了，具体一点的可以参考背包九讲。

算法解释与实现

传统的01背包问题，大致的实现过程如下（时间复杂度：$O(NV)$）：

1
2
3
4
5
for(i=1...N){
	for(j=V...v[i]){
		dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

我们知道这是求最优解的方法，那么前k优解怎么求呢？

貌似不太好想，我们来捋一下传统方法的具体实现思路，看看能不能找到点灵感：

背包问题的解法中，状态$dp[i][j]$是由状态$dp[i-1][j]$和$dp[i-1][j-v[i]]+w[i]$这两个状态转移得到的，那么前k优解的状态转移方程，我们便可以定义为：$dp[i][j][k]$，表示装入前$i$件物品容量最大为$j$时的第$k$大的总价值。

然后正常转移就好了

好吧，具体来说，这里转移状态需要用到归并排序的合并思想：比较$dp[i-1][j]$和$dp[i-1][j-v[i]]+w[i]$，设置一个新数组$num[i]$,利用归并排序合并数组的思想，定义两个变量t1和t2分别指向上述两状态对应的最优值，每次比较将两者中的最优值存入num数组（也即使把这两个状态合并，保证存入num数组的是整个背包的前k优的值 ），随后该值对应状态的t++，，最后再从头到尾把num数组赋给dp数组，因为还需要下一轮状态转移。

那有人会问了：为什么这样就正确呢？我们知道，一个动态规划问题的正确性取决于其是否考虑到了所有状态，对于普通的背包问题，其实就是k==1的情形，而max函数的使用其实就是上述数组合并过程的简化写法，真正的本质还在于这个状态数组合并过程啊！

噢差点忘了，还有就是初始化过程的问题，由于是要求恰好装满背包，因此dp数组的在容量为0的时候的值为0（表示什么都不装，或者说被0装满，是合理的），但其他情形都需要定义为-INF（即不合法状态，因为只要背包有容量了，还必须得全部装满，但初始状态是没有物品给你装的，因此不合法）就行了，这里还是需要消化一下的。

AC代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

int k,v,n,vo[205],va[205];
int dp[5005][55];
int num[55];

int main(){
	cin>>k>>v>>n;
	for(int i=1;i<=n;i++){
		cin>>vo[i]>>va[i];
	}
	for(int i=0;i<=v;i++){
		for(int j=0;j<=k;j++){
			dp[i][j]=-9999999;
		}
	}
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=v;j>=vo[i];j--){
			int t1=1,t2=1;
			for(int m=1;m<=k;m++){
				if(dp[j][t1]>dp[j-vo[i]][t2]+va[i]){
					num[m]=dp[j][t1];
					t1++;
				}else{
					num[m]=dp[j-vo[i]][t2]+va[i];
					t2++;
				}
			}
			for(int o=1;o<=k;o++){
				dp[j][o]=num[o];
			}
		}
	}
	int sum=0;
	for(int i=1;i<=k;i++){
		if(dp[v][i]<=0) break;
		sum+=dp[v][i];
	}
	cout<<sum<<endl;
	return 0;
}
  • 以上就是01背包问题的前k优解的个人理解