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

Question

背包可以承载最大重量，例如 max_wt ；有 n 个给定重量的元素 wt[]和一个值 val[] .我有两个问题(两个问题彼此分开):

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

我的尝试

• 第一个问题我引用了this stackoverflow 帖子，但我能理解的唯一答案是合并两个约束的答案，但我猜它的运行时复杂性会相当大......我在想的是制作一个 dp[i][j][k] ，其中 i 是所选项目的数量，j 是当时选择的最大重量，k 是当时选择的最大音量，然后我的代码核心看起来像
  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 整除的总组合直到该状态，但我无法将其转换为代码。

p.s 请尝试为第二个问题提供自下而上的解决方案，我是动态规划的新手。 ;)

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] )

• 最佳可能值是最大值 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。这只是其中之一。实现也可能不同。维度的经验法则是袋子中的另一个约束或项目中的维度意味着公式中的另一个维度。计数方式的经验法则是您累加而不是求最大值。