本文主要是介绍【完全背包】-HDU-2159-FATE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2159
题目描述：
还是背包，和 0-1 背包差不多，给出物品重量、价值，背包容量，求最大价值和，不同的是这次每种物品有无限个，这就叫完全背包。
解题思路：
一开始没什么思路，本来想把一种物品拆成 m / w[ i ] 个相同物品来看，但觉得太麻烦而且又有可能超时，没去尝试，又去看了背包九讲，，没看懂，于是最后参照了别人的公式和代码，发现和 0-1 背包很类似，就是变成了二维数组，多了一层循环，这是很裸的题了，公式就是如下。不过说实话，，仍然想的不是很明白，还要多做几道题。
AC代码：
/*dp[j][t] = max(dp[j][t],dp[j-w[i]][t-1]+v[i])表示 用掉了j点的忍耐度，并且杀了t个怪后，所获得的最大经验数。
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int v[120],w[120],dp[120][120];int main()
{int n,m,k,s,i,j,t;while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){memset(v,0,sizeof(v));memset(w,0,sizeof(w));memset(dp,0,sizeof(dp));for(i=0;i<k;i++){scanf("%d%d",&v[i],&w[i]);}for(i=0;i<k;i++){for(j=w[i];j<=m;j++){for(t=1;t<=s;t++)dp[j][t]=max(dp[j][t],dp[j-w[i]][t-1]+v[i]);}}int flag=0,ans;for(i=0;i<=m;i++){if(flag)break;for(j=0;j<=s;j++){if(dp[i][j]>=n){flag=1;ans=i;break;}}}if(flag)cout<<m-ans<<endl;elsecout<<-1<<endl;}return 0;
}
AC截图：
这篇关于【完全背包】-HDU-2159-FATE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
