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

问题描述：

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

限制条件：

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

输入：

3

3 4

4 5

2 3

7

输出：

10

#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] );
}

最后

以上就是粗心舞蹈为你收集整理的dp动态规划—完全背包问题的全部内容，希望文章能够帮你解决dp动态规划—完全背包问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。