独特元素的背包
Knapsack with unique elements
我正在尝试解决以下问题：
The knapsack problem is as follows: given a set of integers S={s1,s2,…,sn}, and a given target number T, find a subset of S that adds up exactly to T. For example, within S={1,2,5,9,10} there is a subset that adds up to T=22 but not T=23. Give a correct programming algorithm for knapsack that runs in O(nT) time.
但我唯一能想到的算法是生成所有 1 到 N 的组合并尝试求和（指数时间）。
我无法设计动态规划解决方案，因为我无法重用对象这一事实使这个问题不同于硬币剩余交换问题和一般背包问题。
有人可以帮我解决这个问题，或者至少给我一个提示吗？
O(nT)运行时间给了你提示：做两轴动态规划。也就是说，让 f(a,b) 表示最大总和 <= b 可以用前 a 个整数实现。
f满足递归
f(a,b) = max( f(a-1,b), f(a-1,b-s_a)+s_a )
因为第一个值是不使用 s_a 的最大值，第二个值是包含 s_a 的最大值。从这里开始，DP 算法应该很简单，输出 S 的正确子集也应该如此。
我确实找到了一个解决方案，但时间复杂度为 O(T(n2))。如果我们从下往上做一个table。换句话说，如果我们对数组进行排序并从可用的最大数字开始并创建 table，其中列是目标值，行是提供的数字。我们将需要考虑所有可能的方式的总和，使 i- cost [j] + j 。这将花费 n^2 时间。这与目标相乘。
我正在尝试解决以下问题：
The knapsack problem is as follows: given a set of integers S={s1,s2,…,sn}, and a given target number T, find a subset of S that adds up exactly to T. For example, within S={1,2,5,9,10} there is a subset that adds up to T=22 but not T=23. Give a correct programming algorithm for knapsack that runs in O(nT) time.
但我唯一能想到的算法是生成所有 1 到 N 的组合并尝试求和（指数时间）。
我无法设计动态规划解决方案，因为我无法重用对象这一事实使这个问题不同于硬币剩余交换问题和一般背包问题。
有人可以帮我解决这个问题，或者至少给我一个提示吗？
O(nT)运行时间给了你提示：做两轴动态规划。也就是说，让 f(a,b) 表示最大总和 <= b 可以用前 a 个整数实现。
f满足递归
f(a,b) = max( f(a-1,b), f(a-1,b-s_a)+s_a )
因为第一个值是不使用 s_a 的最大值，第二个值是包含 s_a 的最大值。从这里开始，DP 算法应该很简单，输出 S 的正确子集也应该如此。
我确实找到了一个解决方案，但时间复杂度为 O(T(n2))。如果我们从下往上做一个table。换句话说，如果我们对数组进行排序并从可用的最大数字开始并创建 table，其中列是目标值，行是提供的数字。我们将需要考虑所有可能的方式的总和，使 i- cost [j] + j 。这将花费 n^2 时间。这与目标相乘。