[数据结构与算法]01背包问题及优化一维数组版

一.题目描述

?假设有4个物品体积分别为2,5,3,2，价值分别为30,20 ,40,20

假设你是小偷，背着1个容量为7的包来偷东西，那你肯定要在背包容量允许的情况下，偷到价值高的东西

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?

1.二维数组

用 f [ i ] [ j ] 来表示第i件物品在体积为j时的最大价值，v [ i ] 表示第i件物体体积，w [ i ] 表示第i件物体价值

图表示第i件物品在体积为j时，拿或不拿的最大价值，横为 j，纵为 i

（1）背包容量不够时，放得下的前i个物品的最大价值为前 i -1 个物品的最大价值，即

? ? ? ? f [ i ] [ j ] = f [ i - 1 ] [ j ]

? ?(2)??背包容量够时，有2种选择

? ? ? ? ? 选：f [ i ] [ j ] = f [ i? - 1 ] [ j?-?v [ i ] ]?+?w [ i ] 。
? ? ? ? ? 不选：f [ i ] [ j ]? = f [ i? - 1 ] [ j ]? 。
? ? ? ? ? 我们目的是为了最大价值，则有f [ i ] [ j ]?= max( f [ i?- 1 ] [ j ] , f [ i?- 1 ] [ j - v [ i ] ] + w [ i ] ) 。

代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int main()
{int n ,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];//没放第i个物品 
            if(j>=v[i])//判断能不能放
            {
                f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            } 
        }
    }

    cout<<f[n][m];
    return 0;
}

2.一维数组

从二维表可以看出这能得出任意 i?与 j 合法时的最大价值f [ i ] [ j ] ?，但题目只需要求 f [ n ] [ m ]，因此我们可以用一维数组来做。

这里我用 f [ j ] 来表示 n 件物品在容量 j 时能取得的最大价值

这时有 f [ j ]?= max( f [ j ] , f [ j?- v [ i ] ] + w [ i ] )

这里要注意：优化版的内侧循环必须是逆序的

为什么要逆序

4个物品体积分别为2,5,3,2，价值分别为30,20 ,40,20

我们拿第一行做例子

j = 2时，f [ 2 ] = max ( f [ 2 ] ,f [ 2 - 2 ] +30 ;

j = 4?时， f [ 4 ] = max ( f [ 4 ] ,f [? 4 - 2 ] +30;

这时 f [ 2 ] 我们使用的是刚刚更新的 f [ 2 ] ,也就是 f [ 1?] [ 2 ] ,?而不是上一层的 f [ 0?] [ 2 ] 了

（结合前面的二维数组，手动模拟一下就能懂了）

也就是说，更新点时，右边的需要左边的，左边的不需要右边的，我们从右向左更新，可以保证左边的点不被破坏（之前我一直不理解，一位好大哥给我一语点破）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

接下来，上代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int main()
{int n ,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=v[i];j--)
		{
				f[j]=max(f[j],f[j-v[i]]+w[i]);
		}
	}
	cout<<f[m];
	return 0;
}

谢谢大家的观看，千山万水总是情，三连再走行不行

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

?