关于01背包用dp解的疑问
看了dp解01背包问题，各种算法书上都没提到这个问题。。。我有点疑问，
由于有递归式：m(i,j) = max( m(i + 1, j), m(i+1 ,j - w[i]) + v[i]) ）
其中i代表当前第几种物品，j代表当前背包重量，w[i]代表当前i物品重量，v[i]代表物品的价值。。。
对于m(i+1 ,j - w[i]) + v[i]) 表达式，
当且仅当，w[i], v[i]都为整型的时候才有意义吧。。。
如果都是double类型，那这个数组就没法构成了。。。
可是网上搜了一下，都没有看到相关的话题，想询问一下大大是否是这样。。
[解决办法]
是。非整数的话能离散化那也行，否则的话不同w的数量是随着n而指数递增的。那样dp虽然理论上还是正确的但是没有了优化效率的效果。
这也是为什么这个dp不是强多项式。
[解决办法]
可以这样试下。。。
map<double,double>dp;
for(i=0;i<n;i++)//第i个物品
for(j=m;j>=v[i];j--)//遍历体积
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//进行状态转移
[解决办法]
所以背包问题仍然是NP问题，即没有真正的多项式时间解。
[解决办法]
新学算法,讨论一下/
01背包问题,属于装箱问题吗??一定体积内装入不同体积物体,剩余空间最小.
记得一个类似问题,一张纸,拆成不同[格式]正方形,纸张剩余面积最小..
这个问题,可以用辗转相除法,来解决.即是求长宽的公约数.
辗转相除法可以用来解决体积问题吗,也就是求长宽高的公约数问题.
[解决办法]
没错，double的时候就无法DP了，其实也不仅仅是double，即使是整数，如果都是上亿的，也是无法dp的。
