 /**//*
题意:有钱w,给出n种选择,每种选择有m[i]个物品,但必须先买盒子,价格p[i]
然后给出每种选择的一些物品的价格还有价值 求取得最大值

一开始我想用两个数组,一个记录已经买了box的,一个还没的
这样子转移时有两种
但注意有0的数据,被题目蒙了 .

下面的是龙教主的做法,比较简洁
由于要买box,就先更新一下以前的数组,使得dp[j+p[i]] = _dp[j]
_dp[]最后要更新下,保存最优值
背包变形加状态做,方便点?hdu 3236也是加状态做
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

 inline int max(int a,int b) {return a>b?a:b;}

const int MAXN = 100010;
const int INF = 1000000000;

int dp[MAXN],_dp[MAXN];//within n , without n
int p[51],m[51],c[51][11],v[51][11];

int main()
  {
//freopen("in","r",stdin);
int n,w;
while(~scanf("%d%d",&n,&w))
 {
for(int i=1;i<=n;i++)
 {
scanf("%d%d",&p[i],&m[i]);
for(int j=1;j<=m[i];j++)
scanf("%d%d",&c[i][j],&v[i][j]);
}
for(int j=0;j<=w;j++)dp[j] = _dp[j] = 0;
for(int i=1;i<=n;i++)
 {
for(int j=0;j+p[i]<=w;j++)dp[j+p[i]] = _dp[j];//由于需要先买box,要先更新可以枚举的起点
for(int k=1;k<=m[i];k++)
for(int j=w;j>=p[i]+c[i][k];j--)
dp[j] = max(dp[j],dp[j-c[i][k]]+v[i][k]);
for(int j=p[i];j<=w;j++)//前i次的最优值
_dp[j] = max(_dp[j],dp[j]);
}
int ans = 0;
for(int j=0;j<=w;j++)
ans = max(ans,_dp[j]);
printf("%d\n",ans);
}
return 0;
}

 /**//*

之前的做法跟上面的类似
不过转移时分两种: 从没有box的,从有box的转移过来
for(int j=0;j<=w;j++)
{
dp[now][j] = -INF;
_dp[now][j] = max(dp[pre][j],_dp[pre][j]);
}
for(int k=1;k<=m[i];k++)
for(int j=w;j>=p[i]+c[i][k];j--)
{
//注意有0的数据,所以要按照下面的顺序
//反过来的话,会错,因为dp[now][j-c[i][k]]可能被更新过了,不是之前的值了
dp[now][j] = max(dp[now][j],dp[now][j-c[i][k]]+v[i][k]);
dp[now][j] = max(dp[now][j],_dp[now][j-p[i]-c[i][k]]+v[i][k]);
}
*/
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|