背包問題

description

從t組物品中選出一些物品，放入背包中，求剩餘空間的最小值。

限制條件：從每組物品中挑選物品必須要選取連續的一段。就是說，如果這組物品共有n個： 物品1、物品2、物品3、…、物品n，那麼隻能選取物品i、物品i+1、…、物品j，其中1<=i<=j<=n,或者不選。

input

第一行為兩個用空格隔開的正整數v和t。表示背包的空間和物品的組數。接下來有t行，每行先是一個正整數ni，表示這組物品有ni個，然後ni個正整數，表示每個物品的大小。

output

僅一個數，表示剩餘空間的最小值。

sample input

100 3

3 7 6 8

2 80 70

4 101 108 103 150

sample output

6

data constraint

hint

【樣例說明】

第1組選6、8，第2組選80，第3組不選。

【限制】

60%的資料滿足：1 <= ni <= 10

100%的資料滿足：1 <= ni <= 100，1<=v<=5000，1<=t<=10

分析

可以發現，每組物品，隻能選連續的一段且隻能選一次，是以我們可以想到dp.

b[i,j]表示第i組物品，是否出現連續一段總體積為j的情況。

f[i,j]表示前t組物品，用了j體積裝物品，能裝載的物品的最大值。

然後怎麼去做b[i,j]？

用一個字首和去統計，然後暴力去枚舉判斷就好了。

然後狀态轉移方程：

f[i,j]:=max(f[i,j-1],max(f[i-1,j-k]+k));

1<=i<=n 0<=j<=m 0<=k<=j

最後在這裡面找出一個最大值，然後用v減去max。

程式：