c++ - 如何解决 0-1 背包算法的这些变体？

Question

背包可以承载的最大重量，比如 max_wt ；有 n 个具有给定重量的元素 wt[]和一个值 val[] .我有两个问题(两个问题都是独立的):

• 如果我们可以携带的体积有第二个限制，vol[]，那么我们可以携带的最大值是多少？
• 有多少种方法可以携带总共 z(< n) 个项目，使得它们的值之和可以被一个数字整除，比如 8？

我的尝试

• 对于我提到的第一个问题 this stackoverflow 帖子，但我能理解的唯一答案是两个约束合并的答案，但我猜它的运行时间复杂性会相当大......我在想的是制作一个 dp[i][j][k] ，其中 i 是所选项目的数量，j 是在该点选择的 max-wt ，k 是在该点选择的 max-vol 然后我的代码核心如下所示
  for(i=0 ; i < n ; i++) \\ n is no. of items for(j=0 ; j < n ; j++) for(k=0 ; k < n ; k++) dp[i][j][k] = max( dp[i-1][j][k] , val[i] + dp[i-1][j-wt[j]][k-vol[k]]) ;
  ，这看起来不错，但给了我错误的答案......我无法猜测为什么:(

• 我无法开始思考第二个问题，我的 friend 通过采取三个状态 dp[i][j][k] 来做到这一点，其中 i 和 j 与第一个问题相同(通常的状态) )虽然“k”跟踪所选的总项目，但这个想法并没有进入我的脑海。另外，状态会存储什么，它通常存储在经典背包问题中给定状态之前可能的最大值，这里我猜状态会存储可被 8 整除的总组合直到该状态，但我无法将其转换为代码。

请尝试为第二个问题提供一个自下而上的解决方案，我对动态编程非常陌生。 ;)

Answer 1

二维背包问题

• 让n是项目的数量
• 让val[i]是 i 的值-第一项
• 让w[i]是 i 的重量-第一项
• 让v[i]是 i 的体积-第一项
• 让T[i,j,k]成为第一中的最佳值(value)i元素并具有精确重量 j和卷k 。 T可以用其他方式定义，但这个定义给出了一个简短的公式。

寻找最佳值(value)

• T[0,j,k] = 0

• T[i,j,k] = T[i-1,j,k] ，当 j<w[i]或k<v[i] ，否则:

• T[i,j,k] = max( T[i-1,j,k] , T[i-1,j-w[i],k-i] + val[i] )

• 最佳可能值为 max T[n,j,k]对于所有 j 和 k

实现说明

• 首先初始化所有基本情况j和k

• 循环i从 1 到 n 并与基于 1 的数组索引保持一致

• 循环j从 1 到最大可能权重，即所有权重的总和，例如w[1]+w[2]+...w[n]

• 循环k从 1 到最大可能音量

计算用精确数量的项目获取精确值的方法数量

• 让S[i,j,k,l]是第一个 i 的方式数量元素可以精确排列重量j ，值k ，和l项目。

• S[0,j,k,l] = 0 ，除了S[0,0,0,0] = 1

• S[i,j,k,l] = S[i-1,j,k,l] + S[i-1,j-w[i],k-val[i],l-1]

• 获取精确值的方法数 y正好使用z items 是 T[n,j,y,z] 的总和对于所有人j

观察结果

有很多方法可以看待这些问题并定义状态 T 和 S。这只是其中之一。实现方式也可能有所不同。尺寸的经验法则是，袋子中的另一个约束或项目中的尺寸意味着公式中的另一个尺寸。计算方式的经验法则是相加而不是求最大值。