HDU3449_变种01背包_多个篮子

题目大意:          提供给你几个篮子,每个篮子有价格,还有其可以容纳的物品的个数,然后可容纳的物品有各自需要的价格(注意篮子有多个,每个篮子里面的物品可以不同,种数也可以不同),然后物品都有自己的权值(可以理解为重量之类的属性)。要买篮子里面的物品,你必须要先买这些物品所属的篮子。然后你一开始有一定的钱,要求你买到物品的权值最大(可以理解为重量最多)。 解题思路:          咋一看,这货是分组背包?细想下,这又不是,是依赖型背包?好像有点儿像依赖型的。可是篮子也木有权重啊?         不晓得,最后看了别人的思路才知道,用01背包来做就可以了。不过状态转移方程略微坑爹。        用一个二维数组dp[0][]来表示当前买到的最优解,表示还没有买下当前这个篮子。dp[1][]来表示把当前这个篮子买下后,得到的最优解。          dp[1][k]=max(dp[1][k],dp[1][k-box[i].p_s[j]]+box[i].v_s[j]);//对这个盒子里面的进行01背包         dp[1][k]=max(dp[1][k],dp[0][k-box[i].p_s[j]-box[i].p]+box[i].v_s[j]);//看看是否买这个盒子          dp[0][j]=max(dp[0][j],dp[1][j]);//将上面循环中买到当前盒子的最优解赋值到总体dp,即dp[0][]中 代码:
#include
#include
#define max(x,y) x>y? x:y
const int MAX=55;
const int inf=0x7fffffff;
using namespace std;

typedef struct l
{
	int p;
	int num;
	int p_s[MAX];
	int v_s[MAX];
}L;
int dp[2][100005];

int main(void)
{
	L box[MAX];
	int n,tal;
	while(cin>>n>>tal)
	{
		int i,j;
		for(i=0;i>box[i].p>>box[i].num;
			for(j=0;j>box[i].p_s[j]>>box[i].v_s[j];
		}
		//dp
		memset(dp[0],0,sizeof(dp[0]));
		for(i=0;i=box[i].p_s[j];k--)
				{
					dp[1][k]=max(dp[1][k],dp[1][k-box[i].p_s[j]]+box[i].v_s[j]);//对这个盒子里面的进行01背包
					if(k>=box[i].p+box[i].p_s[j])
						dp[1][k]=max(dp[1][k],dp[0][k-box[i].p_s[j]-box[i].p]+box[i].v_s[j]);//看看是否买这个盒子
				}
			for(j=0;j<=tal;j++)
				dp[0][j]=max(dp[0][j],dp[1][j]);//将上面循环中买到当前盒子的最优解赋值到总体dp,即dp[0][]中
		}
		cout<<*max_element(dp[0],dp[0]+tal+1)<

 
原文地址:https://www.cnblogs.com/cchun/p/2520192.html