各位小哥哥,大家有女友吗?没有的,请自觉退出,谢谢合做,女生的话,大家随意web
大家有没有遇到这样的问题 :就是大家要出去玩,干啥我就不说的太清了,反正大家就是想出去玩,可是,大家的背包过小了,装不下全部的东西,可是因为你的女友的心情彻底取决于你带的全部物品的总价值高不高,你为了让你女友开心,你就开始学习了这个算法。。。。嘿嘿嘿算法
全部题目的前提:假设大家有n件物品,背包能够装下物品最大重量是m,第 i 件物品的价值是v[i],重量是w[i](是否是感受无从下手,来来来,爸爸帮你,,,)数组
原材料:w[],v[]数组记录状态,n,m就很少说了,dp[]来记录当前最优解ide
for(i=1;i<=n;i++) for(j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(i=1;i<=n;i++) for(j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
for(i=1;i<=n;i++) { for(j=m;j>=1;j--) { k=min(j/w[i],num[i]); for(t=1;t<=k;t++) if(k*w[i]<=j) dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]); } }
获得的就是最优解的一个数组,dp[m]就是能放入的最大价值
什么?你还没看明白?来来来,这里有详解>>>>>>>>>>>>通常比较笨的人,才会点我svg
什么?你没有女友?来来来,出门右拐,那里有一个墙,你去自闭吧,想一想为啥别人都有,就你没有,啧啧啧学习