2133庆功会 简单动态规划(注释很详细) (外加图解)

解题思路:经典的动态规划问题.

我的理解:本题加入了参数s,表示一个物体最多可以买多少件,其实就相当于是01背包中,多加入了几个相同的物体,所以这道题实质上和第2131题:01背包是一样的.

注意事项:本题由于数据量较大,用最普通的dp数组,会出现一个问题:空间不够,所以就要想办法优化dp数组.

有两个办法:1.重复利用一个数组 2.滚动利用数组

重复利用一个数组的方法好像已经有人说了,那我就来说说更好理解的滚动利用数组的办法;

参考代码:

#include<bits/stdc++.h>

using namespace std;

int W[5005],V[5005];
//价格和价值
//waste value

int w,v,s;
//价格,价值,最大数量

int n;
//相当于01背包中,有n件物品

int M,N;
//Money拨款金额 Number礼物种类

int i,j;

int dp[2][5000005];
//普通dp数组dp[i][j]的含义:在前i件物品中取价格为j时的最大总价值
//这里是滚动利用dp数组

int main()
{
	scanf("%d %d",&N,&M);
	//这里的N我们之后不会用到,M会用到
	getchar();

	while(scanf("%d %d %d",&w,&v,&s) != EOF)
	 {
		while(s)
		//转化为01背包
		{
			s--;
			i++;
			W[i] = w;
			V[i] = v;
		}
 	}

	n = i;
	//相当于01背包中,有n件物品

	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= M; j++)
		{
			if(j < W[i])
			{
				dp[i & 1][j] = dp[(i-1) & 1][j];
				/*注意这里的 &i,就是数组的滚动利用*/
				/*当i为奇数,i的二进制最低位上是1,进行&1操作后得1,
				当i为奇数,i的二进制最低位上是0,进行&1操作后得0;*/
				/*可以结合下图理解*/
			}
			else
			{
				dp[i & 1][j] = max(dp[(i-1) & 1][j-W[i]] + V[i], dp[(i-1) & 1][j]);
			}
		}
	}

	cout << dp[n & 1][M];
	//n如果为奇数 ,n&1就等于1; 为偶数就等于0
	//而如果n为奇数,滚动数组刚好就停在下面一行(dp[1][]),如果为偶数就在上面一行(dpp[0][])
	//故运算契合需求

	return 0;
}