[动态规划] 组合背包问题

题目描述

有个财主收藏了大量的宝物。为防止被盗，他将宝物藏在离家不太远一个海岛上的不同洞穴内，有些洞内放了一件宝物，有些洞存放了多件，并绘制了藏宝图。但藏宝图不慎被一个海盗发现，他详细知道了每件宝物所在的洞穴。好在财主事先做了进一步的防范措施：万一有人进入一个洞内窃取宝物，最多只能取走洞内的一件宝物，而且不能让其再进入同一个洞内。海盗决定驾着他的小船去盗宝，但船承载货物的重量受限。已知每件宝物的重量和价值，请你根据船的载重量，推算海盗在每个洞只能进去一次的情况下，这一趟盗走宝物可能导致财主最大价值的损失是多少？

关于输入

第一行两个整数m,n（1<=m,n<=1000），分别是船的载货重量（海盗自身的重量忽略不计）和宝物总件数。两个整数以空格间隔
接下来n行，每行3个数，分别表示各件宝物的重量、价值和所在洞的编号。均为整数，且以空格间隔。

关于输出

一个整数值，为所盗宝物可能的最大总价值。

例子输入

30 3
15 8 1
10 5 1
48 400 2

例子输出

8

#include <iostream>
using namespace std;

int m,n,l[1005]={0},w[1005],v[1005],pos[1005][1005],x;
int len=0;
int dp[100005];

int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",w+i,v+i,&x);
		l[x]++;
		pos[x][l[x]]=i;
		len=max(x,len);
	}
	for(int i=1;i<=len;i++)
		for(int j=m;j>=1;j--){
			for(int k=1;k<=l[i];k++){
				if(w[pos[i][k]]<=j){
					dp[j]=max(dp[j],dp[j-w[pos[i][k]]]+v[pos[i][k]]);
				}
			}
		}
	printf("%d\n",dp[m]);
	return 0;
}

解题分析

本题是一道经典的组合背包问题，不同于01背包和完全背包问题，我们增加了一重限制，即我们将物品分组了，每组物品中我们最多只能取一个物品，在这种情况下，我们又该如何去解决问题呢？

首先，我们不妨定义dp[i][j]为考虑前i个洞穴，背包容量为j的情况下我们能得到的最大价值。根据容斥原理，我们可以比较轻松地得到递推的关系，dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，其中w[i]是我们从第i个洞穴取出的物品的重量(weight)，v[i]是这个物品的价值(value)。

但是，在真正的应用场景中，这样直接递推是不合适的，我们还需要更多的数组辅助我们，此外，我们需要用三层循环去给dp数组打表，不断更新dp数组。而且，考虑到内存的要求，我们仿照01背包问题的状态压缩和滚动数组的方法去优化我们的内存。

此外，还需要理解for循环顺序不一样对dp数组打表的影响，不妨手动模拟填表一下，我们可以发现，如果我们在外层枚举背包容量，而内层枚举每一个物品，那么我们得到的dp[i][j]就是在背包容量为j的情况下，考虑前i个物品，仅取出一个物品能得到的最大价值。

代码实现