-1

问题：给定一个整数数组 A[]，长度 = n 和一个给定的整数值 TARGET。找到满足其总和小于 TARGET 且最接近该 TARGET 的子序列（可能不连续）。

例如：A[] = [10, -2, 3, 7]。目标 = 14。答案 = {10, 3}

我在 Hackerrank 挑战中遇到了这个问题，我无法找出任何多项式时间解决方案，它首先听起来对一些动态规划问题很熟悉，但在这种情况下，条件“不大于”和“最近”似乎消除了该解决方案。

从我遵循动态规划方法的第一个想法开始，在 i-problem (i=0->n-1) 处，我们需要评估所有包含 A[i] 或不包含 A[i] 的子序列，后者被称为 S[i-1]，所以只关注以 A[i] 作为最后一个元素的所有子序列。

我们不能仅仅依赖以前解决的问题（0-> i-1），因为我们需要的总和必须小于并且最接近目标可能不会从较小的解决方案中产生，它可能是从第二个解决方案产生的，第三个加上最后一个元素 A[i]，并且遍历所有包含 A[i] 的子序列将需要遍历所有 2^i - 1 个子集，不包括单个集合 {A[i]}。

对这类问题有什么建议吗？

4

3 回答 3

0

这是背包问题的一个例子，其中“值”等于物品的重量，而 TARGET 是背包的容量。

应用关于输入大小在伪多项式时间内运行的动态规划解决方案。

于 2015-03-23T06:10:13.633 回答
0

这不是很困难的问题，比背包问题更容易。下一个代码解决您的问题：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include<cstring>
#include <math.h>
#include<cstdio>
#include<string>
#include <queue>
#include <list>

using namespace std;


int main(){
    int dp[100000];
    int way[100000];
    memset(dp,0,sizeof(dp));
    memset(way,0,sizeof(way));
    int *dpTmp = dp+50000;
    int *wayTmp = way+50000;
    dpTmp[0] = 1;
    wayTmp[0] = -1;
    int A[]={10,-2, 3, 7};
    int TARGET = 14;
    int n=4;
    for(int i=0; i<n; i++){
        if(A[i]<0){
            for(int j=-50000; j<50000; j++){
                if(dpTmp[j] == 1 && dpTmp[j+A[i]] == 0){
                    dpTmp[j+A[i]] = 1;
                    wayTmp[j+A[i]] = i;
                }
            }
        }else{
            for(int j=49999; j>=-50000; j--){
                if(dpTmp[j] == 1 && dpTmp[j+A[i]] == 0){
                    dpTmp[j+A[i]] = 1;
                    wayTmp[j+A[i]] = i;
                }
            }
        }
    }
    int inc = 1;
    if(TARGET>0){
        inc = -1;
    }else{
        inc = 1;
    }
    TARGET += inc;
    while(dpTmp[TARGET] == 0) TARGET+=inc;
    cout<<TARGET<<endl;
    while(wayTmp[TARGET] != -1){
        cout<<A[wayTmp[TARGET]]<<" ";
        TARGET -= A[wayTmp[TARGET]];
    }
    cout<<endl;
    return 0;
}
于 2015-03-23T09:31:16.300 回答
0 
/**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with each of size A[i]
     * @return: The maximum total size of items under the limit of size m
     */

int backPack(int m, vector<int> A) {
        // use one dimensional V to represent two dimensional m
        vector<int> V(m+1,0);
        for(int i=0;i<A.size();i++)
        {
            for(int j=m;j>=A[i];j--)
            {
                V[j] = max(V[j], V[j-A[i]] + A[i]);
            }
        }
        return V[m];
    }
于 2016-09-16T04:14:24.123 回答