dp动态规划—完全背包问题

78 阅读 0 评论 52 点赞

我是靠谱客的博主粗心舞蹈，这篇文章主要介绍dp动态规划—完全背包问题，现在分享给大家，希望可以做个参考。

问题描述：

有n种重量和价值分别为wi, vi 的物品。从这些物品中挑选总重量不超过MaxValue的物品，求挑选物品价值总和的最大值。在这里，每种物品可以挑选任意多件。

限制条件：

1 <= n <= 100 , 1 <= wi, vi <= 100 , 1 <= MaxValue <= 10000

输入：

3 4

4 5

2 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
43
44
45
#include <cstdio>
#include <algorithm>
#define MAXN 100
using namespace std;
void solve();	/* 此函数是主函数中递推方法的简化版*/
int n, MaxValue;
int w[MAXN+1], v[MAXN+1];
int dp[MAXN+1][MAXN+1];
int main()
{
scanf("%d", &n );
for( int i=0; i<n; i++ )
scanf("%d%d", &w[i], &v[i] );
scanf("%d", &MaxValue );
for( int i=0; i<n; i++ )
{
for( int j=0; j<=MaxValue; j++ )
{
for( int k=0; k*w[i] <= j; k++ )	// 利用k的累加性，可以找到当前物品选的最大数量
dp[i+1][j] = max( dp[i+1][j], dp[i][j -k*w[i]] + k*w[i] );
// max() 选出的是不选当前物品与选当前物品k个中，价值较大的一个
// dp[i][j -k*w[i]] + k*w[i] 表示丛前i种物品中挑选出总重量不超过j -k*w[i]的总价值得最大值
// 且加上当前能选的物品的数量的最大值
}
}
printf("%dn", dp[n][MaxValue] );
return 0;
}
/* 在dp[i+1][j]的计算中选择 k(k>=1)个的情况，与在dp[i+1][j-w[i]]的计算中选择k-1个的情况是相同的
所以，dp[i+1][j]的递推中k>=1部分的计算在dp[i+1][j-w[i]]的计算中完成了 */
void solve()
{
for( int i=0; i<n; i++ )
{
for( int j=0; j<=MaxValue; j++ )
{
if( j <w[i] )	// 如果不能选则前i+1个与前i个情况相同
dp[i+1][j] = dp[i][j];
else
dp[i+1][j] = max( dp[i][j], dp[i+1][j-w[i]] + v[i] );
}
}
printf("%dn", dp[n][MaxValue] );
}