0/1 배낭 증인 생성

Question

배낭 알고리즘을 풀기 위해 사용하고있는 배낭 클래스를 작성했습니다. 이 클래스는 작동하고 동적 프로그래밍 알고리즘을 사용하여 문제를 해결합니다.

최대 값을 찾기 위해 선형 O (W) 공간을 사용하도록 코드에서 일부 최적화를 구현했지만 증인을 찾으려고 할 때 여전히 불리언 테이블을 유지하는 O (nW) 공간이 필요합니다.

최소 용량의 배낭과 O (nW)의 동일한 복잡성을 가진 배낭의 증인을 찾을 수 있는지 누군가가 말해 줄 수 있습니까? W는 배낭 용량입니다.

코드에 몇 가지 최적화가 더 있다고 생각되는 경우 알려주십시오.

class Knapsack{ 
private: 
    vector<int> value, weight, answer, DP; 
    vector<bool> isin; 
    int capacity; 

public: 
    Knapsack(vector<int> value, vector<int> weight, int capacity, bool needWitness){ 
    this->value = value; 
    this->weight = weight; 
    this->capacity = capacity; 

    this->answer.clear(); this->isin.clear(); this->DP.clear(); 
    this->DP.resize(capacity + 1, false); 

    if (needWitness){ 
     this->isin.resize(value.size() * (capacity + 1), false); 
     solveWithWitness(); 
    } 
    else{ 
     solveWithoutWitness(); 
    } 

    } 

    void solveWithoutWitness(){ 
    for (int i = 0; i < value.size(); i++){ 
     for (int w = capacity; w >= weight[i]; w--){ 
     if (DP[w] < value[i] + DP[w - weight[i]]){ 
      DP[w] = value[i] + DP[w - weight[i]]; 
     } 
     } 
    } 
    } 

    void solveWithWitness(){ 
    for (int i = 0; i < value.size(); i++){ 
     for (int w = capacity; w >= weight[i]; w--){ 
     if (DP[w] < value[i] + DP[w - weight[i]]){ 
      DP[w] = value[i] + DP[w - weight[i]]; 
      isin[ i*capacity + w ] = true; 
     } 
     } 
    } 
    int position = value.size()-1; 
    int w = capacity; 
    while (position >= 0){ 
     if (isin[ position*capacity + w ]){ 
     answer.push_back(position); 
     w -= weight[position]; 
     } 
     position--; 
    } 
    } 


    vector<int> getWitness(){ 
    return this->answer; 
    } 

    int solution(){ 
    return DP[capacity]; 
    } 

}; 

Answer 1

당신은 사방 O의를 사용하고, 그래서 당신에게 여전히 시간을 만족 당신이 원하는 경계 조금 복잡하고 어색 이론 솔루션을 제공 할 수 있습니다 :

실행없이 목격 DP를 n/2 단계; 첫 번째 n/2 개 항목 만 사용하여 W 가중치 중 어느 것이 도달 가능한지 알려줍니다. 이제 남은 n/2 단계에 대해 DP를 실행하여 첫 번째 n/2 항목에서 각 셀에 도달하는 데 필요한 가중치를 추적합니다.

반복적 인 방법으로 순차적으로이 절차를 적용하면 T (n, W) < = 2T (n/2, W) + O (nW)와 같은 시간이 반복됩니다. log (n) W). 그 정도면 충분하지 않습니다.

하지만 첫 번째 n/2 개 항목에서 얼마나 많은 무게가 필요한지 알아 냈습니다. 그걸 불러. DP 배열의 첫 번째 항목 만 신경 써야합니다. 따라서 처음 절반 재귀는 T (n/2, w) 시간이 걸리고, 후반 재귀는 T (n/2, W-w) 시간이 걸리고 거기에 도착하는 데 필요한 작업은 O (nW) 시간이 걸립니다.

폼 T의 재발 용액 (N, W) < = 최대 (0 < = < = W w) (w N/2) T + T (N/2, WW에) + O (nW)는 실제로 O (nW)입니다. 처음에는 n-by-W 사각형을 0으로 상상하여 직관적으로 볼 수 있습니다. n '항목과 가중치 W'를 갖는 재귀 배낭 호출은 일부 n'-W '서브 사각형의 각 항목에 1을 더합니다. 그런 다음 첫 번째 재귀 수준은 총 nW, 두 번째 수준 nW/2, 세 번째 nW/4 등을 추가하여 기하학적 계열을 제공합니다.