题目描述：
一个盗贼嵌入一间装满珠宝的仓库，仓库大小N×M (N,M<=10)，每个格子都放着一颗钻石，重量为Wij 。盗贼有一个背包，能装V重量的物品，他希望能在L(L<=7)时间内取得尽量多的钻石。不幸的是，某些格子被安装上了监视器，监视器以Ti(1<=Ti<=6)的周期工作，若盗贼不幸被监视器发现，那么他将被捕获。盗贼和监视器从0时刻开始活动。
分析：
若抛开背包的重量限制，盗贼每个单位时间能有5种走法（4个方向和停留），最多走7步，最多的搜索量也只有5^7≈80000。
我们可以考虑深度优先搜索所有可能的路径，不需要太强的剪枝也行。
接下来就是要处理，当盗贼的某条路径搜索完毕时，如何判断当前路径上最多能获得多少钻石？
显然是典型的01背包问题。
我试了一下按照最经典O(m^2)的算法，即以物品重量为阶段进行DP，结果TLE了（此题唯一一个TLE就是我贡献的>_<||）
其原因很明显，题目没告诉钻石重量的范围，有可能很大。但是物品数量却很小（最大7），而O(2^n)的枚举显然不行，只能换另一种DP方案……
这里主要讲一下这种物品数量很少的01背包问题的动态规划，这个算法差不多是O(n^3)的：
1，数组f[i]保存当前能够得到的重量，n为f[]中的元素个数。
初始时，f[0]=0，n=1，即当前有1个可以得到的重量0。
2，枚举每一个物品a[i]，对于当前每一个能得到的重量f[j]，
若a[i]+f[j]没有超重，且还没有在f[]中存在，那么把a[i]+f[j]加入到f[i]数组中，n++。
3，在判断新加入的重量是否存在于f[]中时，可以用Hash优化，时间复杂度降到O(n^2)，很好很优秀。
这个题目这样做没多大问题。我用的O(n^3)的DP＋很弱剪枝的搜索，0.06sAC了～：）
其实在搜索的时候还可以有一个优化剪枝，即在走深搜每一个节点时，用一个广搜来判断不考虑监视器的情况下，所省余的时间最多能取得多少钻石。若这个值加上已经取得的值小于当前搜索的最优结果，那么该节点可以剪掉。
珍贵的代码～ 只贴DP那段好了 ：）
int f[M];
int exist(int f[],int n,int x){
int i;
for(i=0;i<n;i++) if(f[i]==x) return 1;
return 0;
}
int getjew(int b[],int w)
{
int i,j,k;
int n=1,m,maxw=0;
clr(f);
f[0]=0;
for(i=0;i<w;i++){ //each item
m=n;
for(j=0;j<m;j++) //add to f[j]
if(b[i]+f[j]<=v && !exist(f,n,b[i]+f[j])){
f[n++]=b[i]+f[j];
if(b[i]+f[j]>maxw) maxw=b[i]+f[j];
}
}
return maxw;
}