【剖析】0-1背包算法

傷城~ 2022-06-13 00:12 136阅读 0赞

# 0-1背包 #

何为0-1背包？通俗的讲就是背包问题，一个包要么背这件物品，要么不背这件物品，0和1体现了要么背要么就不背，每件物品都有重量和价值，怎样选择物品才能获得最大点的价值，这个问题我们可以通过动态规划的方法进行巧妙的解决。

我们用当前得物品重量和包的剩余重量进行比较，如果书包剩余重量小于当前的物品重量，就直接进行下一个武平的匹配，如果书包剩余重量大于当前物品重量，有两种选择，要么装，要么不装，这个选择体现它的价值，通过递归很巧妙的实现了这个思想，代码如下：

int count2 = 0;
    int Knapsack(int *w, int *v, int i, int len, int weight)
    {
    	count2++;
    	if (w == NULL || v == NULL) return 0;
    	if (i == len)
    		return  weight >= w[i] ? v[i] : 0;//最后只有一个的元素时的最大值
    	if (i < len)//大于一个元素
    	{
    		if (w[i]>weight)
    			return Knapsack(w, v, i + 1, len, weight);
    		else
    		{
    			int a =Knapsack(w, v, i + 1, len, weight);
    			int b = Knapsack(w, v, i + 1, len, weight - w[i]) + v[i];
    			return a > b ? a : b;
    		}
    	}
    	return 0;
    }

我们发现这个代码有很多的重复计算，那么怎么样消除重复项呢？我们借助二维数组，代码如下：

int count1 = 0;
    int Knapsack_e(int *w, int *v, int i, int n, int j, int **m)
    {
    	count1++;
    	if (i == n)
    	{
    		m[i][j] = j >= w[n] ? v[n] : 0;
    		return m[i][j];
    	}
    	else if (m[i][j] > 0) return m[i][j];
    	{
    		if (j<w[i])
    		{
    			m[i][j] = Knapsack_e(w, v, i + 1, j, n, m);
    		}
    		else
    		{
    			int a = Knapsack_e(w, v, i + 1, j, n, m);
    			int b = Knapsack_e(w, v, i + 1, j - w[i], n, m) + v[i];
    			m[i][j] = a>b ? a : b;
    		}
    		return m[i][j];
    	}
    }

这两个都是递归实现，那么循环的方法怎样实现呢？代码如下：

int count3;
    int Knapsack1(int *w, int *v, int **c, int n,int weight)
    {
    	int i, j;
    	i=n;
    	for (j = 1; j <= weight; j++)
    	{
    		c[i][j] = w[i] > j ? 0 : v[i];
    	}
    	for (i = n - 1; i >= 1; i--)
    	{
    		for (j = 1; j <= weight; j++)
    		{
    			if (w[i] > j)
    				c[i][j] = c[i + 1][j];
    			else
    			{
    				c[i][j] = Max1(c[i + 1][j], c[i + 1][j - w[i]] + v[i]);
    			}
    		}
    	}
    	return c[1][weight];
    }