algorithm - 0-1 重量等于容量而不是小于或等于容量的背包

Question

在背包问题中，我们通常会尝试最大化背包中 cargo 的值(value)，同时保持 cargo 的总重量 <= C，其中 C 是背包的容量。当 cargo 的总重量正好等于背包的容量=C时，如何解决？

Answer 1

您要解决的问题是相同的，但约束更严格。相同的 DP 解决方案将是:-

DP(n,W) = 0;
Valid(n,W) = false;

if(Valid(n-1,W)) {

    DP(n,W) = DP(n-1,W);
    Valid(n,W) = true;
}

if(Valid(n-1,W-weight[n])) {

     DP(n,W) = max(DP(n,W),DP(n-1,W-weight[n])+value[n]);
     Valid(n,W) = true;
}