用动态规划算法的变形方法——备忘录方法，解决0-1背包问题

2022-09-10 09:45:49

使用备忘录方法解决0-1背包问题：
1.跟直接递归很相似，该算法能将递归遇到的子问题的解保存在一个表中，以便下一个递归遇到同样的子问题时快速求解。

2.为了区分一个子问题是否已经求解，可以通过查表的方式来判断，若子问题对应的表中元素的值为一个初始特殊值，说明该子问题还未求解；否则，表明该子问题曾经已求解过，直接获取子问题的解，不需要递归求解该值。

3.备忘录算法与动态规划算法的区别有：

（1）备忘录方法的递归方式是自顶向下，而动态规划算法则是自底向上递归的。

（2）备忘录方法的控制结构与直接递归方法的控制结构相同，而动态规划算法的控制结构与循环迭代的控制结构相同。

（3）备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免相同子问题的重复求解；而动态规划算法则是建立一个表格，从最小的子问题开始向上求解较大的子问题，把每一个子问题的解全部填入表格中，直到表格中出现原问题的解为止。它们两者的共同特点是对子问题的求解都只解了一次，并记录了答案。

（4）当一个问题的所有子问题都至少要解一次时，用动态规划比用备忘录方法要好，此时，动态规划算法没有任何多余的计算。当子问题空间中的部分问题可不必求解时，用备忘录方法较有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。

以下是源代码：

#include "stdafx.h"
#include <iostream>
#include <ctime>
using namespace std;

const int N = 4; //物品数量
const int C = 7; //背包容量
int w[N] = {2,3,5,2};
int v[N] = {6,4,8,4};
int m[N][C+1]; //记录子问题的解的表格
int x[N];

void initial()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= C; j++)
		{
			m[i][j] = -1;
		}
	}
}

//以下使用备忘录法求解0-1背包问题（物品重量为整型）
int KnapsackMemoMethod(int i, int capacity)
{
	if(m[i][capacity] != -1)
		return m[i][capacity]; //使用m[i][capacity]需要检查两个下标是否出界
	int result = 0;
	if(i == N-1)
		if(capacity >= w[i])
		{
			m[i][capacity] = v[i];
			return v[i];
		}			
		else
		{
			m[i][capacity] = 0;
			return 0;
		}

	else
	{
		if(capacity >= w[i])
		{
			int selected = KnapsackMemoMethod(i+1,capacity-w[i])+v[i];
			int unselected = KnapsackMemoMethod(i+1,capacity);
			result = selected > unselected ? selected : unselected;
			m[i][capacity] = result;
			return result;
		}
		else //capacity < w[i]
		{
			result = KnapsackMemoMethod(i+1,capacity);
			m[i][capacity] = result;
			return result;
		}
			
	}
}

void Trace(int i, int capacity)
{
	if(i == N-1)
	{	
		if(m[i][capacity] == v[i])
			x[i] = 1;
		else
		{
			x[i] = 0;
		}
		return;
	}
	else
	{		
		if (m[i][capacity] == m[i+1][capacity])
		{
			x[i] = 0;
			Trace(i+1, capacity);
		}
		else
		{
			x[i] = 1;
			Trace(i+1, capacity - w[i]);
		}
	}	
}

int main()
{
        initial();
	cout<<KnapsackMemoMethod(0,C)<<endl;
	Trace(0,C);
	for (int i = 0; i < N; i++)
	{
		cout<<x[i]<<" ";
	}
	cout<<endl;
	system("pause");
	return 0;
}

运行结果如下：

1 0 1 0