我如何解决 0-1 背包算法的这些变化？
How do i solve these variations of the 0-1 knapsack algorithm?
背包可以承载的最大重量，比如说max_wt；有 n 个给定重量 wt[] 和值 val[] 的物品。我有两个问题（两个问题彼此分开）：
- 如果我们可以携带的体积有第二个限制，vol[ ]，我们可以携带的最大值是多少？
- 有多少种方法可以携带总共 z(< n) 个项目，使得它们的值的总和可以被一个数字整除，比如 8？
我的尝试
对于第一个问题，我参考了 this Whosebug post，但我唯一能理解的答案是合并了两个约束，但是 运行 我想那的时间复杂度会相当大......我在想的是制作一个 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]]) ;
，这似乎没问题，但给了我错误的答案......我猜不出为什么:(
第二题想不出来，我朋友是取三个状态dp[i][j][k]做的，其中i和j和第一题一样（通常的那些）虽然 'k' 跟踪所选项目的总数，但这个想法并没有进入我的脑海。另外，在经典背包问题中，状态存储会存储什么，它通常存储可能的最大值直到给定状态，在这里我猜一个状态将存储可被 8 整除的总组合直到该状态，但我无法将其转换为代码。
p.s 请尝试为第二个问题提供一个自下而上的解决方案，我是动态规划的新手。 ;)
二维背包问题
- 设
n为项目数
- 设
val[i] 为第 i 项的值
- 设
w[i] 为第 i 项的重量
- 设
v[i] 为第 i 项 的体积
- 让
T[i,j,k] 成为前 i 项中的最佳值，并且具有 完全 重量 j 和体积 k. T 可以用其他方式定义，但这个定义给出了一个简短的公式。
寻找最佳价值
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] )
对于所有 j 和 k
T[n,j,k]
实施说明
首先为所有 j 和 k
从1到n循环i并与基于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]
使用 z 项获得精确值的方法数 y 是所有 j[=46= 的 T[n,j,y,z] 的总和]
观察
有很多方法可以查看这些问题并定义状态 T 和 S。这只是其中之一。实现也可能不同。维度的经验法则是袋子中的另一个约束或项目中的维度意味着公式中的另一个维度。计算方法的经验法则是你加起来而不是找到最大值。
背包可以承载的最大重量，比如说max_wt；有 n 个给定重量 wt[] 和值 val[] 的物品。我有两个问题（两个问题彼此分开）：
- 如果我们可以携带的体积有第二个限制，vol[ ]，我们可以携带的最大值是多少？
- 有多少种方法可以携带总共 z(< n) 个项目，使得它们的值的总和可以被一个数字整除，比如 8？
我的尝试
对于第一个问题，我参考了 this Whosebug post，但我唯一能理解的答案是合并了两个约束，但是 运行 我想那的时间复杂度会相当大......我在想的是制作一个
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]]) ;
，这似乎没问题，但给了我错误的答案......我猜不出为什么:(第二题想不出来，我朋友是取三个状态dp[i][j][k]做的，其中i和j和第一题一样（通常的那些）虽然 'k' 跟踪所选项目的总数，但这个想法并没有进入我的脑海。另外，在经典背包问题中，状态存储会存储什么，它通常存储可能的最大值直到给定状态，在这里我猜一个状态将存储可被 8 整除的总组合直到该状态，但我无法将其转换为代码。
p.s 请尝试为第二个问题提供一个自下而上的解决方案，我是动态规划的新手。 ;)
二维背包问题
- 设
n为项目数 - 设
val[i]为第i项的值 - 设
w[i]为第i项的重量 - 设
v[i]为第i项 的体积
- 让
T[i,j,k]成为前i项中的最佳值，并且具有 完全 重量j和体积k.T可以用其他方式定义，但这个定义给出了一个简短的公式。
寻找最佳价值
T[0,j,k] = 0T[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] )对于所有 j 和 k
，最佳可能值为最大值
T[n,j,k]
实施说明
首先为所有
j和k 初始化基本案例
从1到n循环
i并与基于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] = 1S[i,j,k,l] = S[i-1,j,k,l] + S[i-1,j-w[i],k-val[i],l-1]使用
z项获得精确值的方法数y是所有j[=46= 的T[n,j,y,z]的总和]
观察
有很多方法可以查看这些问题并定义状态 T 和 S。这只是其中之一。实现也可能不同。维度的经验法则是袋子中的另一个约束或项目中的维度意味着公式中的另一个维度。计算方法的经验法则是你加起来而不是找到最大值。