-1

問題: 整数配列 A[]、長さ = n、整数値 TARGET が与えられた場合。その合計が TARGET よりも小さく、その TARGET に最も近いことを満足するサブシーケンス (連続していない可能性があります) を見つけます。

例: A[] = [10, -2, 3, 7]. ターゲット = 14. 答え = {10, 3}

私は Hackerrank チャレンジでこの問題に遭遇しました。多項式時間の解を見つけることができませんでした。最初は、いくつかの動的計画法の問題に非常によく知られているように思えますが、この場合、「次よりも大きくない」および「最も近い」という条件が排除されているように見えます。その解決策。

動的計画法のアプローチに従う私の最初の考えから、i 問題 (i=0->n-1) で、A[i] を含むか含まないすべてのサブシーケンスを評価する必要があります。後者は A[i] を含みます。は S[i-1] として知られているため、最後の要素として A[i] を持つすべてのサブシーケンスに注目してください。

以前に解決した問題 (0->i-1) に頼ることができない場合、必要な合計がターゲットよりも小さく、ターゲットに最も近い必要があるため、小さなソリューションからは得られない可能性があり、2 番目の問題から生成される可能性があります。 、3 番目に最後の要素 A[i] を追加し、A[i] を含むすべてのサブシーケンスを反復するには、単一のセット {A[i]} を除いて、2^i - 1 個のサブセットすべてを通過する必要があります。

この種の問題に関する提案はありますか？

4

3 に答える 3

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

これは、「値」がアイテムの重量に等しく、TARGET がナップザックの容量であるナップザック問題のケースです。

入力サイズに関して疑似多項式時間で実行される動的計画法ソリューションを適用します。

于 2015-03-23T06:10:13.633 に答える