正和的最小长度子序列 <= K

Question

相反的问题：

正和 <= K 的最大长度子序列实际上是 标准 01 背包问题。

它的解决方案非常简单：

int solve(const vector<int> &A, int K) {
int dp[A.size()+1][K+1];
int i, j;
// Base Cases
for(i=0; i<= K; i++)
dp[0][i] = 0;
for(i=0; i<= A.size(); i++)
dp[i][0] = 0;

for(i=1; i <= A.size(); i++)
{
for(j=1; j<= K; j++)
{
dp[i][j] = dp[i-1][j];
if(A[i-1] <= j)
dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-A[i-1]]);
}
}
return dp[A.size()][K]

我很难思考如何按照相同的思路实现总和 <= K 的最小长度子序列。

例：

A = [14, 10, 4]
K = 14
Minimum Length Subsequence = 14
Maximum Length Subsequence = 10, 4 (Arrived from Knapsack)

这当然不像将最大值更改为最小值那么容易，因为答案将始终是基本情况。这让我想到，我们需要调整基本情况吗？我被困在这里，需要一些推动。

关于应该如何解决这个问题的任何想法？

Answer 1

将总和替换为有序对(sum, length)。 现在应用您知道的先前算法。 顺序是字典编纂的，按总和然后按长度。 你正试图接近(target_sum, 0).

现在最接近的"总和"将是正差最小的最短子序列。

Answer 2

下面的代码片段显示了我所说的筛子是什么意思。这是一个简单的解决方案，可能对大量输入没有用。它不像筛子来寻找素数，它只包含真或假，而更像是组合及其总和的字典，例如：

{value: 14, components: [4, 10]}  

如果你不熟悉Javascript，数组的行为更像是带有字符串键的关联数组或字典(这就是为什么需要Number转换(，并且for in只在数组稀疏时才迭代具有值的元素。此外，slice和concat创建数组的副本。

function minSub(array, target) {
var sieve = [[]];
for (var i in array) {
var temp = [];
for (var j in sieve) {
var val = Number(j) + array[i];
if (!sieve[val] || sieve[val].length > sieve[j].length + 1) {
temp[val] = sieve[j].concat([array[i]]);
}
}
for (var j in temp) {
if (Number(j) <= target) {
sieve[j] = temp[j].slice();
}
}
}
var max = 0;
for (var j in sieve) {
if (Number(j) > max) {
max = Number(j);
}
}
return sieve[max];
}
console.log(minSub([4, 10, 14], 14));
console.log(minSub([0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0], 8));

请注意，与我在评论中的建议相反，按降序对输入进行排序并不能保证首先找到形成值的最简单组合;每当遇到筛子中已经存在的值时，您必须检查组件的数量; 例如，使用输入：

{8, 4, 3, 2, 1}

你会发现这个组合：

{value: 9, components: [4, 3, 2]}

在找到之前：

{value: 9, components: [8, 1]}

Answer 3

我认为这符合您正在寻找的内容。我们必须比你制定的最大子序列更小心，以检查是否可以达到一个总和。在这个公式中，dp[i][j]是最小的子序列总和j，考虑了最多A[i]的元素(所以i不是子序列长度(。

JavaScript 代码(仅经过轻度测试(：

function solve(A, K) {
let i,j;
let dp = new Array(length);
for (i=0; i<A.length; i++)
dp[i] = new Array(K + 1);
// Base Cases
for(i=0; i<A.length; i++)
dp[i][0] = 0;
for (i=0; i<A.length; i++){
// Exact match
if (A[i] == K)
return 1;
// We can reach this sum with only one element
if (A[i] < K)
dp[i][A[i]] = 1;

// There are no previously achieved sums
if (i == 0)
continue;

for (j=1; j<=K; j++){
dp[i][j] = dp[i][j] || dp[i - 1][j];
if (A[i] <= j){
dp[i][j] = Math.min(
dp[i][j] || Infinity,
1 + (dp[i - 1][j - A[i]] || Infinity)
);
}
}
}

for (i=K; i>=0; i--)
if (![undefined, Infinity].includes(dp[A.length - 1][i]))
return dp[A.length - 1][i];
}
console.log(solve([1,2,3,4,5,6,7,8,9,10], 11));
console.log(solve([14,10,4], 14));
console.log(solve([0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0], 8));
console.log(solve([7,7,2,3],15))