連續背包 (背包套背包）

【問題描述】
從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; 
}