HDU2191 dp

HDU2191悼念512汶川大地震遇难同胞

题目大意

1
2
3
一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。 
请问:你用有限的资金最多能采购多少公斤粮食呢?
[以下题解转自网上]

题解1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//多重背包转换成01背包来做
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int W,n;
int w[2005],v[2005];
int dp[20005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&W,&n);
int cnt=0;
int a,b,c;
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
while(c--)
{
w[cnt]=a;
v[cnt]=b;
cnt++;
}
}
for(int i=0;i<cnt;i++)
for(int j=W;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d\n",dp[W]);
}
return 0;
}

题解2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//未优化的多重背包  我们定义 dp[i+1][j] 表示前i中物品(包括i)中重量不超过j的所能得到的最大价值。则状态转移方程为 dp[i+1][j]=max(dp[i][j-w[i]*k])+v[k] k=(0...g[i]);g[i]表示物品i共有几个。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int W,n;
int w[105],v[105],g[105];
int dp[205][20005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&W,&n);

for(int i=0;i<n;i++)
{
scanf("%d%d%d",&w[i],&v[i],&g[i]);
}

for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
{
dp[i+1][j]=dp[i][j];
for(int k=1;k<=g[i];k++)
if(j>=k*w[i]) dp[i+1][j]=max(dp[i+1][j],dp[i][j-w[i]*k]+v[i]*k);
}
printf("%d\n",dp[n][W]);
}
return 0;
}

题解3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//记忆化搜索
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=105;
int n,W;
int w[MAXN],v[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int dfs(int dep,int wei)
{
if(dp[dep][wei]!=-1)
return dp[dep][wei];
if(dep==n)
{
return dp[dep][wei]=0;
}
int res=0;
for(int k=0;k<=b[dep]&&wei>=k*w[dep];k++)
{
res=max(res,dfs(dep+1,wei-w[dep]*k)+v[dep]*k);
}
return dp[dep][wei]=res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(dp,-1,sizeof(dp));
scanf("%d%d",&W,&n);
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&w[i],&v[i],&b[i]);
}

printf("%d\n",dfs(0,W));
}

return 0;
}
文章目录
  1. 1. HDU2191悼念512汶川大地震遇难同胞
    1. 1.1. 题目大意
    2. 1.2. 题解1
    3. 1.3. 题解2
    4. 1.4. 题解3