就像是
最大重量 3
Value Weight
1955 1
2000 5
101 1
拿第一个和第三个。但找不到总价值。1955+101。
我使用背包 0-1。有没有从数组中找到 1955+101
就像是
最大重量 3
Value Weight
1955 1
2000 5
101 1
拿第一个和第三个。但找不到总价值。1955+101。
我使用背包 0-1。有没有从数组中找到 1955+101
假设您有 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,它将做出该决定。如果您的决定涉及获取特定项目,则打印该项目的索引。
希望这可以帮助 :)