HDU 2191 珍惜现在，感恩生活（多重背包）

本文主要是介绍HDU 2191 珍惜现在，感恩生活（多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目 ： click here ~~

题目分析：就一个多重背包，在输入的时候进行二进制拆分，接下来就与01背包一样处理了。关于二进制拆分，这里讲解的不错~

AC_CODE

int v[1002] , c[1002];
int dp[1002];
int main()
{int t;cin >> t;while(t--){int n ,m , i , j , a , b , d ,k = 0;cin >> n >> m;for(i =1;i <= m;i++){scanf("%d%d%d",&a ,&b ,&d);for(j = 1;j <= d;j <<= 1)//进行二进制拆分{c[k] = j*a;v[k++] = j*b;d -= j;}if(d > 0){c[k] =  d*a;v[k++] = d*b;}}memset(dp , 0 , sizeof(dp));for(i = 0;i < k;i++)for(j = n;j >= c[i];j--)dp[j] =  max(dp[j] , dp[j - c[i]] + v[i]);cout << dp[n] << endl;}return 0;
}

这篇关于HDU 2191 珍惜现在，感恩生活（多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---