本文主要是介绍hiho 完全背包（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开还是最经典的完全背包问题，完全背包和01背包还是有区别的，完全背包中每一个物品可以选择多次，最后推出的递推公式跟01背包的基本上算是一样的，还是设一个二维数组dp[][]，dp[i+1][j]表示从前i个奖品中选出总奖券不超过j时总价值的最大值，w[]数组表示每个奖品需要的奖券数，v[]数组表示每个奖券的价值；
递推关系：|dp[0][j]=0;
|dp[i+1][j]=max{dp[i][j-k*w[i]]+k*v[i]|k>=0};
重点来了，上面的公式可以继续转换：
max{dp[i][j-k*w[i]]+k*v[i]|k>=0}
=max(dp[i][j],max{dp[i][j-k*w[i]]+k*v[i]|k>=1})
=max(dp[i][j],max{dp[i][(j-w[i])-k*w[i]]+k*v[i]|k>=0}+v[i])
=max{dp[i][j],dp[i+1][j-w[i]]+v[i]}
由此可以看出，完全背包的递推公式和01背包的递推公式惊人的相似，就是红色的字体01背包中改为i，太容易记了
今天跑步了，ajie监督着跑的，一口气让我跑了10圈
累死了，还好最后犒劳犒劳我明天有比赛，省赛前的训练，是组队的，加油！
好了，贴代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int dp[505][100005];
int w[505],v[505];
int max(int m,int n)
{return m>n?m:n;
}
void solve(int n,int m)
{int i,j;for(i=0;i<n;i++)for(j=0;j<=m;j++){if(j<w[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);}printf("%d",dp[n][m]);
}
int main()
{int n,m,i;scanf("%d%d",&n,&m);for(i=0; i<n; i++)scanf("%d%d",&w[i],&v[i]);solve(n,m);return 0;
}
这篇关于hiho 完全背包（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
