pascal 01背包的容量很大时怎么做啊

背包问题一般都是f[i,j]动规做！
但是今天遇到一个题，它背包的容量是100,000,000也就是1亿，不管是时间还是空间都没法做！求解释！
但是大数据的物品个数最多就是200个！是不是可以搜索？如果可以，有没有强剪枝？

01背包的空间压缩只能压缩至O(V),可是V过大.这样压缩根本没用..时间复杂度也是没有办法降低的.
但是我在想,10^8的背包,200个物品,这说明物品要么大小差别很小但是平均都很大,这种情况下可以离散化一下,忽略(具体怎么忽略我还没完整的想法)低位数字,指数级减少数据规模.
要么说明这些物体大小差别很大,那么,只要分大小件物品分别背包就可以了,因为如果物品大小差别2-3个数量级,就不可能相互影响(200个,低位要进位需要多少个数字累加呢,假设都是5(超过舍入)200*5 = 1000,只能影响3个数量级),不过具体应该还有要注意的地方..
..这些说的都是临时YY的,重来没用过..因为从来就没听过10^8的背包- -也许是题目有别的方法吗?

嗯。。。。搜索题，搜索只与N有关，是2 的N 次方，再加些剪枝，最多就30+了，至于N=200，不行吧，有可能物品重量有特点吧，或者可以分割的，那是贪心题，如果不是那我就不会了。。。。。。

01背包一般都用f[j]优化空间，f[j]=max(f[j],f[j-c[i]]+w[i])，循环时倒着来，即 for i:=1 to n do for j:=v downto c[i] do f[j]=max(f[j],f[j-c[i]]+w[i]); 楼下讲的有道理，我把回答改了算了。 LZ把题目给一下吧，让我们做做

这是动态规划 program knapsack02; const maxm=200;maxn=30; type ar=array[1..maxn] of integer; var m,n,j,i:integer; c,w:ar; f:array[0..maxn,0..maxm] of integer; function max(x,y:integer):integer; begin if x>y then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])｛如果当前背包可以装入背包i且装入后最大则装入i｝ else f[i,j]:=f[i-1,j]; end; writeln(f[n,m]); 参考资料：数据结构