【C语言DP动态规划】背包问题（01背包，多重背包，完全背包）

75 阅读 0 评论 50 点赞

我是靠谱客的博主唠叨月饼，这篇文章主要介绍【C语言DP动态规划】背包问题（01背包，多重背包，完全背包），现在分享给大家，希望可以做个参考。

一.每种物品仅有一件，可以选择放或不放。（01背包）

有N件物品和一个容量为V的背包。第i件物品的费用是a[i].w，价值是a[i].value。求解将哪些物品装入背包可使价值总和最大。

动态规划
　　我们定义一个二维数组，其中每个元素代表一个状态，即前i个物体中放入体积为j背包中最大价值。
　　其中，dp[0][j]=0,dp[i][0]=0(因为无论体积为0，还是没有物品都不能存放，所以最大价值为0);
　　转移方程：

复制代码

1
2
3
4
5
if (a[i].w<j)
dp[i][j] = dp[i-1][j] //背包装不下第i个物体，目前只能靠前i-1个物体装包
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-Vi] + Wi)

程序

复制代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
struct node {
int w,value;
int flag;
}a[100];
int dp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
int i,j;
for(i=1;i<=p;i++)
{
for(j=1;j<=q;j++)
{
if(a[i].w>j)
dp[i][j]=dp[i-1][j];
else if(dp[i-1][j]>dp[i-1][j-a[i].w])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j-a[i].w]+a[i].value;
}
}
printf("最大价值为%dn",dp[p][q]);
}
void trans(int p,int q)
{
int i=p;
while(p!=0)
{
if(dp[p][q]>dp[p-1][q])
{
c[p]=1;
q-=a[p].w;
}
p=p-1;
}
for(i;i>=1;i--)
{
printf("第%d个物品 是否存放？%d",i,c[i]);
printf("n");
}
}
int main()
{
int i,p,q;
scanf("%d %d",&p,&q);
for(i=1;i<=p;i++)
{
scanf("%d %d",&a[i].w,&a[i].value);
a[i].flag=i;
}
dpdist(p,q);
trans(p,q);
return 0;
}

二.每种物品都固定个数，使达到最大价值。（多重背包）

多加一层循环判断个数即可
程序

复制代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
struct node {
int w,value,x;
int flag;
}a[100];
int dp[100][100]={0};
int cp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
int i,j,k;
for(i=1;i<=p;i++)
{
for(j=1;j<=q;j++)
{
for(k=0;k*a[i].value<=j&&k<=a[i].x;k++)
{
if(dp[i][j]<dp[i-1][j-k*a[i].w]+k*a[i].value)
{
dp[i][j]=dp[i-1][j-k*a[i].w]+k*a[i].value;
}
cp[i][j]=k;
}
}
}
printf("最大价值为%dn",dp[p][q]);
}
void trans(int p,int q)
{
int i=p;
while(p!=0)
{
if(dp[p][q]>dp[p-1][q])
{
c[p]=cp[p][q];
q-=a[p].w;
}
p=p-1;
}
for(i;i>=1;i--)
{
printf("第%d个物品存放%d个？%d",i,c[i]);
printf("n");
}
}
int main()
{
int i,p,q;
scanf("%d %d",&p,&q);
for(i=1;i<=p;i++)
{
scanf("%d %d %d",&a[i].w,&a[i].value,&a[i].x);
a[i].flag=i;
}
dpdist(p,q);
trans(p,q);
return 0;
}

三.每种物品数量不限，使达到最大价值。（完全背包）

程序

复制代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
struct node {
int w,value;
int flag;
}a[100];
int dp[100][100]={0};
int cp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
int i,j,k;
for(i=1;i<=p;i++)
{
for(j=1;j<=q;j++)
{
for(k=0;k*a[i].value<=j;k++)
{
if(dp[i][j]<dp[i-1][j-k*a[i].w]+k*a[i].value)
{
dp[i][j]=dp[i-1][j-k*a[i].w]+k*a[i].value;
}
cp[i][j]=k;
}
}
}
printf("最大价值为%dn",dp[p][q]);
}
void trans(int p,int q)
{
int i=p;
while(p!=0)
{
if(dp[p][q]>dp[p-1][q])
{
c[p]=cp[p][q];
q-=a[p].w;
}
p=p-1;
}
for(i;i>=1;i--)
{
printf("第%d个物品存放%d个？%d",i,c[i]);
printf("n");
}
}
int main()
{
int i,p,q;
scanf("%d %d",&p,&q);
for(i=1;i<=p;i++)
{
scanf("%d %d",&a[i].w,&a[i].value);
a[i].flag=i;
}
dpdist(p,q);
trans(p,q);
return 0;
}