POJ-3624-背包问题

它这个问题问的是，在有限的容量下，能装下的最大价值是多少。

所以我们可以递归求解，记忆性递归，用二维数组，但是这样的话就会超内存，所以我们只能用动规来写，而且不能开二维数组，

只能用滚动数组。

我们设一个F数组，大小为13000，它存的是容积为m的背包可放下的最大价值。

我们先假设一个二维数组F [ i ][ j ] ，它表示的意思是，背包里放 i 个物品，最大价值为 j ，它的最大价值。

我们可以知道 F [ i ][ j ] = max ( F [ i-1][ j ] ,F[ i-1][ j-w[i] ] +value [ i ] ) 。

它的意思是，F [ i ][ j ]的值来自于如果不选第 i 个物品，放下值为 j 的包的最大价值，和如果选第 i 个物品，背包里放下 j-weight[i] 大小物品的最大价值和第 i 个物品价值之和，经过比较之后最大的那个值。

我们对于F [ i ][ j ]可以选也可以不选，不选的话，它的价值就是F [ i-1 ][ j ] ，选的话它的价值就是F[ i-1][ j-w[i] ] +value [ i ] ，就是在原背包容积减去 i 物品的重量之后，放入 i-1 个物品的最大价值与 i 物品的价值之和。

不过有个条件，如果 j-w[i] >=0 ，我们才比较求解，小于它的话，我们就让它等于它的上一行同列的值。

好，那么问题来了，这个问题怎么在一维数组中求解呢？

首先我们要知道，在二维数组里面它们的形态：

F[ i-1][ j-w[i] ] F [ i-1][ j ]

F [ i ][ j ] F[ i ][ 2j-w[i] ]

所以说，对于F [ i-1 ][ j ] ，我们还是有用的，我们要用来求右下角的那个元素，我们不能正向，由小到大直接把F [ i-1 ][ j ]覆盖掉，我们应该在用完它时候，再覆盖掉，所以我们从右向左求，就不会伤害任何值了。

代码如下：

#include <iostream>

using namespace std;

int w[3600],d[3600],F[13000];

int main()

{

	int n,m;

	cin>>n>>m;

	for (int i=1;i<=n;i++) {

		cin>>w[i]>>d[i];

	}

	for (int i=1;i<=n;i++) {

		for (int j=m;j>=w[i];j--) {

			F[j]=max(F[j],F[j-w[i]]+d[i]);

		}

	}

	cout<<F[m]<<endl;

	return 0;

 }

巴特西

POJ-3624-背包问题

最新文章

热门文章