洛谷P1776 宝物筛选 题解

从题目中可以看出我们要帮小$F$决定带走哪些宝物，每种宝物都有它的重量和每种宝物的价值以及每种宝物的个数，而且需要使采集车能装下的的宝物的价值总和最大。有了这些数据，我们就可以显而易见地看出这题应该使用多重背包dp来解这题。

30分

使用二维数组$dp[i][j]$表示拥有前$i$种宝物，采集车的最大载重不超过$j$时的最大总价值

六要素

• 决策:带走$0$~$m_i$个同一种的宝物
• $i$（前$i$个宝物）为阶段
• $dp[i]$（前$i$种宝物）$[j]$（采集车的最大载重不超过$j$）为状态，表明当前最大总价值
• $dp[0][0]$=$0$为初始值
• $dp[m]$（所有宝物）$[t]$（最大载重）为目标值
• 状态转移方程

dp[i][j]=max(dp[i][j]/*不放此宝物*/,dp[i-1][j-k*h[i]]+k*u[i]/*选取$k$个当前宝物*/);

30分 $Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 10000
using namespace std;
int n,w,u[MAX],h[MAX],m[MAX],dp[MAX][MAX];
//n:宝物种数;w:采集车的最大载重;u:每种宝物的价值;h:每种宝物的重量,m:每种宝物件数
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;++i)scanf("%d%d%d",&u[i],&h[i],&m[i]);
	for(int i=1;i<=n;++i)//循环前$i$种宝物
	{
		for(int j=1;j<=w;j++)//循环采集车的最大载重
		{
			for(int k=0;k<=m[i]&&k*h[i]<=j;k++)//循环前k个物品
			{
				dp[i][j]=max(dp[i][j]/*不放此宝物*/,dp[i-1][j-k*h[i]]+k*u[i]/*选取$k$个当前宝物*/);
			}
		}
	}
	printf("%d",dp[n][w]);
    return 0;
}

但是由于最朴素的多重背包dp的时间复杂度太大了，所以我们要进行二进制优化

一维数组

使用一维数组$f[i]$表示可用时间不超过$i$的最大总价值

六要素

• 决策:带走$0$~$m_i$个同一种的宝物

• $i$（前$i$个宝物）为阶段

• $dp[i]$:采集车的最大载重为 $i$ 时的收集的宝物的最大价值

• $dp[0]$=$0$为初始值

• $dp$$[t]$（最大载重）为目标值

• 状态转移方程

dp[j]=max(dp[j]/*不放此宝物*/,dp[j-w[i]]+v[i]/*选取$k$个当前宝物*/);

二进制优化 $Ac$ $Code$

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 100001
using namespace std;
int n,wi,v[MAX],w[MAX],dp[MAX],a,b,c,cnt=0;
//n:宝物种数;wi:采集车的最大载重;v:每种宝物的价值;w:每种宝物的重量
//dp[i]:采集车的最大载重为i时的收集的宝物的最大价值
//a,b,c:价值为a,重量为b,每种宝物有c件;cnt:宝物总个数(不是种数)
int main()
{
	scanf("%d%d",&n,&wi);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		for(int j=1;j<=c;++j)
		{
			cnt++;
			v[cnt]=j*a;
			w[cnt]=j*b;
			c-=j;
		}
		if(c)
		{
			cnt++;
			v[cnt]=a*c;
			w[cnt]=b*c;
		}
	}
	for(int i=1;i<=cnt;++i)//循环第$i$个宝物
	{
		for(int j=wi;j>=w[i];--j)//循环采集车的最大载重
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d",dp[wi]);
    return 0;
}

浏览次数：