c++ - 背包 DP 如何求取值的总数？

Question

就像是

最大重量 3

Value Weight 

1955    1
2000    5
101     1

拿第一个和第三个。但找不到总价值。1955+101。

我使用背包 0-1。有没有从数组中找到 1955+101

Answer 1

假设您有 2 个数组values和wt，以及另一个变量initial_capacity，它是背包的最大容量。然后，您需要首先调用dp函数，该函数计算您可以实现的maxValue 。重构函数告诉您应该采取哪些项目来达到 maxValue 。

int dp(int position, int weight)
{
    if(position == no_of_items) return 0;
    if(mem[position][weight] != -1) return mem[position][weight];

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    return mem[position][weight] = max(r1, r2);
}

void reconstruct(int position, int weight)
{
    if(position == no_of_items) return;

    int r1 = dp(position + 1, weight);
    int r2 = dp(position + 1, weight - wt[position]) + value[position];

    if(r2 > r1)
    {
        cout << "Take item at position : " << position << endl;
        reconstruct(position + 1, weight - wt[position]);
    }
    else
    {
        reconstruct(position + 1, weight);
    }
}

int main()
{
    //read input here
    memset(mem, -1);
    int maxValue = dp(0, initial_capacity);
    cout << "Max value : " << maxValue << endl;
    reconstruct(0, initial_capacity);
}

请注意，重建以贪婪的方式工作。哪个决定（接受该项目或跳过该项目）会导致 maxValue，它将做出该决定。如果您的决定涉及获取特定项目，则打印该项目的索引。

希望这可以帮助 ：）