背包算法变异

3 回答

• 1

  这被称为“多重约束背包问题”（MKP，偶尔呈现为d-KP） . 它可以在假多项式时间内解决，就像常规的背包问题一样，但是你需要一个二维表而不是一个 .

  回复于 2024-04-23T16:18:21+08:00
• 1

  将m [i，wa，wb]定义为最大值（此处的项目数），可以通过 a s小于或等于 wa 的总和以及 b s之和小于或等于 wb 来实现，使用最多 i 的项目 .

  m[i,wa,wb] = m[i-1,wa,wb]
  

  如果 item[i].a > wa 或 item[i].b > wb

  要么

  m[i,wa,wb] =  max (m[i-1, wb, wb], m[i-1, wa - item[i].a, wb - item[i].b] + 1)
  

  如果 item[i].a <= wa 和 item[i].b <= wb

  回复于 2024-04-23T16:18:21+08:00
• 2

  这是一个可能对您有帮助的递推方程： -

  if(Items[N].b<=Wa && Items[N].b<=Wa)
      Value(N,Wa,Wb) = max(1+Value(N-1,Wa-Items[N].a,Wb-Items[N].b),Value(N-1,Wa,Wb)) 
  
  else Value(N,Wa,Wb) = Value(N-1,Wa,Wb)
  
  Where Wa = Current capacity of A sack & Wb of B sack
        N = no of items considered
  

  注意：您可以在递归解决方案上使用哈希表实现，这将阻止三维数组 .

  回复于 2024-04-23T16:18:21+08:00