连续背包 (背包套背包）

Posted on by
内容目录

连续背包（bag）

【问题描述】

从T组物品中选出一些物品，放入背包中，求剩余空间的最小值。

限制条件：从每组物品中挑选物品必须要选取连续的一段。就是说，如果这组物品共有n个： 物品1、物品2、物品3、…、物品n，那么只能选取物品i、物品i+1、…、物品j，其中1<=i<=j<=n,或者不选。

【输入】

第一行为两个用空格隔开的正整数v和T。表示背包的空间和物品的组数。

接下来有T行，每行先是一个正整数ni，表示这组物品有ni个，然后ni个正整数，表示每个物品的大小。

【输出】

 仅一个数，表示剩余空间的最小值。

【输入输出样例】

bag.in

100 3

3 7 6 8

2 80 70

4 101 108 103150

 

bag.out

6

 

【输入输出样例解释】

 第1组选6、8，第2组选80，第3组不选。

【限制】

60%的数据满足：1 <= ni <= 10

100%的数据满足：1 <= ni <= 100，1<=v<=5000，1<=T<=10

 

对每一段背包

再对各段背包

注意单步中Vmax=V[i-1]+sum[ni]

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXNI (100+10)
#define MAXV (500000+10)
#define MAXN (10+10)
int T,n,v,sum[MAXNI]={0},a[MAXNI],A[MAXN][MAXV]={0};
bool f[MAXN][MAXV]={0};
int main()
{
	freopen("bag.in","r",stdin);
	freopen("bag.out","w",stdout);
	scanf("%d%d",&v,&T);
//	v=v*10;
	f[0][0]=1;
	for (int i=1;i<=T;i++)
	{
		scanf("%d",&n);
		sum[0]=0;
		for (int j=1;j<=n;j++) {scanf("%d",&a[j]);if (a[j]>v/*/10*/) a[j]=0; sum[j]=sum[j-1]+a[j];}
		//for (int j=1;j<=n;j++) printf("%d ",sum[j]);
		for (int k=0;k<=v+sum[n];k++)
			for (int j=n;j>=0;j--)
			{
				if (k-sum[j]<0) continue;
				if (f[i-1][k-sum[j]])
				{
					f[i][k]=1;
					A[i][k]=j;
					break;
				}
			}
		for (int k=0;k<=v+sum[n];k++)
			for (int j=A[i][k]-1;j>=1;j--)
			{
				f[i][k-sum[j]]=f[i][k]||f[i][k-sum[j]];
			}



		//cout<<endl;
	}
//	v/=10;
	int i=v;
	while (!f[T][i])
	{
		i--;
	}
	printf("%dn",v-i);
/*
	for (int i=0;i<=T;i++)
	{
		for (int j=0;j<=v;j++)
			if (f[i][j]) cout<<i<<','<<j<<' ';
		cout<<'n';
	}

	while (1);
*/	return 0;
}