连续背包（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("%d\n",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;}
如果觉得《连续背包 (背包套背包）》对你有帮助，请点赞、收藏，并留下你的观点哦！
