连续背包 (背包套背包）

【问题描述】
从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]

[cpp]
#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;
}

补充：软件开发 , C++ ,