0-1揹包中的最終重量？

Question

您如何找到0-1揹包問題DP解決方案的最優集合的最終權重？給定一組'n'項目，每個項目都有自己的權重和價值。

#include <cstdio> 
#include <vector> 
#include <algorithm> 
#include <map> 
using namespace std; 

vector < pair <int, int> > arr; 
map < pair <int, int>, int > hash_memo; 
pair <int, int> temp; 

int knapsack(int N, int budget) 
{ 
    int a, b=0; 
    pair <int, int> local; 
    if((!N) || (!budget)) return 0; 
    local.first = N; 
    local.second = budget; 
    if(hash_memo[local]) return hash_memo[local]; 

    a = knapsack(N-1, budget); 
    if(budget >= arr[N-1].first) 
    { 
     b = arr[N-1].second + knapsack(N-1, budget - arr[N-1].first); 
    } 

    if(a>b) 
    { 
     hash_memo[local] = a; 
     return a; 
    } 
    hash_memo[local] = b; 
    return b; 
} 

int main() 
{ 
int budget, N, a, b; 

    while(1) 
    { 
     scanf("%d %d", &budget, &N); 
     if((!budget) && (!N)) break; 

     arr.clear(); 
     hash_memo.clear(); 
     for(int i=0; i<N; i++) 
     { 
      scanf("%d %d", &a, &b); 
      if(b==0) continue; 
      temp.first = a; temp.second = b; 
      arr.push_back(temp); 
     } 

     int max_value = knapsack(N, budget); 
     printf("%d\n", max_value); 
    } 

return 0; 
} 

以上就是「MAX_VALUE」給出了最優解集的最終值0-1揹包問題的代碼。你如何找出'max_weight'？ 'N'是項目的數量，'預算'是可以考慮的最大權重。

Answer 1

返回一對含重量和價值值：

pair<int, int> knapsack(int N, int budget) 
{ 
    if((!N) || (!budget)) return pair<int, int>(0, 0); 

    pair<int, int> local(N, budget); 
    if(hash_memo[local].second) return hash_memo[local]; 

    pair<int, int> b = pair<int, int>(0, 0); 
    pair<int, int> a = knapsack(N-1, budget); 
    if(budget >= arr[N-1].first) 
    { 
     pair<int, int> c = knapsack(N-1, budget - arr[N-1].first); 
     b = pair<int, int>(c.first + arr[N-1].first, c.second + arr[N-1].second); 
    } 

    if(a.second > b.second) 
    { 
     return hash_memo[local] = a; 
    } 
    return hash_memo[local] = b; 
}