带有一个附加约束的背包
这就是古老而著名的背包问题：背包问题
这里我有一个有约束的背包问题。
我有一个大小为W=100000000和N=100项的背包，我为它写了动态解。我的算法复杂度为O(100000000*100)，这在时间和空间上都太大了，但这里有一个条件，W≤50000或max1≤I≤nvi≤500。所以如果我的背包大小超过50000，我的项的最大值是有限的。
所以现在我想知道如何用这个条件我认为背包问题取决于背包的大小和物品的数量，那么物品的值如何才能改变我的算法呢？
共有1个答案
与其创建大小w*n的表，其中每个条目d[x][i]指示使用第一个i项最多可以使用x权重获得的最佳值（最高），不如使用下面的表，其中d[x][i]元素获得x值所需的最小权重：
D(0,i) = 0 i>0
D(x,0) = infinity x > 0
D(x,i) = infinity x<0 or i<0
D(x,i) = min{ D(x,i-1), D(x-value[i],i-1) + weight[i])
完成后，查找max{x D(x，n)<=W)}-这是可以获得的最高值，最多使用W权重，并通过对DP矩阵的最后一行进行线性扫描来完成。
通过对数据的一次扫描来检查您需要的变体。
-
我试图找出一个有四个约束的背包的逻辑。我想做一个程序，你输入你想在一餐中摄入的卡路里、脂肪、碳水化合物和蛋白质，它会在一个可能的食物列表中查找符合输入标准的最接近的食物组合。 示例 我有这些东西 4盎司牛肉（231卡路里，15克脂肪，0克碳水化合物，22克蛋白质） 1/2杯燕麦粥（260卡路里，2克脂肪，58克碳水化合物，10克蛋白质） 1/2杯黑豆（120卡路里，.5克脂肪，23克碳水化合物，7
-
假设我有一个表示篮球运动员及其姓名、位置、费用和预计得分的元组列表，
-
此约束是否在分数计算器()中。它是否可以检查一个解决方案中的进程组是否被分配到相同的CPU并给它打分？ 有没有其他更好的方法，比如使用ValueSelector？ 并且我在缺省情况下得到了一个解决方案，即使进程不能分配给CPU（因为限制）。计划者就是这样工作的吗？
-
我的视图控制器中有几个视图，当检测到向上滑动时向上移动，然后当检测到向下滑动时向下移动。我使用CGRectOffset通过调整y原点来强制视图移动。我现在使用IB对视图施加了约束，我不确定移动视图的最佳方法是什么，以便它们最终在iPhone 5、6和6上的正确位置。 目前我正在做这样的事情： 用比值改变常数是否更好？因此，对于上面的约束，不使用338，这样做是否更好:
-
有效的解决方案路由的约束是： 考虑到第二个约束，路由中遍历的所有边的权重之和必须是图中可能的最高值。 所选路由中必须访问过N个顶点（包括起始和结束顶点）。 通常，图形将有大量的顶点和边，所以尝试所有的可能性是不可能的，需要相当有效的算法。