描述:石头收藏家小明在徒步登山的时候发现了一堆美丽的石头。这些石头价值不菲，但是都很重，小明自身的力气有限，一次只能拿他拿得动的一部分。每块石头的重量不同，价值也不同。问小明在力所能及的情况下能拿走价值多少的石头。 说明：小明只能搬运一次。 例如：小明只能拿得动 10 kg，每块石头的重量分别为2kg，3kg，5kg，7kg，对应的价值分别为 1万，5万，2万，4万。小明能拿的是 3kg 以及 7kg 的石头，价值 9 万。 输入 使用分号(;)分隔三组数据。 第一组为一个整数，表示小明一次能搬运的最大重量。 第二组为一个使用逗号(,)分隔的数组，表示每块石头的重量。 第三组为一个使用逗号(,)分隔的数组，表示每块石头的对应的价值。
输出 一个整数，表示小明这次能带回去的石头的总价。
输入样例 10;2,3,5,7;1,5,2,4 输出样例 9
动态规划 dp[i,w]表示背包容量为w时，i个物品最优解的总价值,可得到以下推导公式 i=0或w=0, dp[i,w]=0; wi>w, dp[i,w]=dp[i-1,w]; i>0且wi<=w, dp[i,w]=max{dp[i-1,w-wi}+vi,dp[i-1,w]} 其中dp[i-1,w-wi}+vi表示 选择第i个物品时,所获得的最优解, dp[i-1,w]表示不选择第i个物品时的最优解.
实现时dp[i,w]可以用一个二维数组来实现,为了压缩空间,也可以使用一维数组.
二维数组下的求解顺序，物品数1—>n, 背包容量1—>w。要使用一维数组，背包容量要采用倒序，即w—>1, 只有这样对于方程dp[j] = max{( dp[j], dp (j-w[i] ) + v[i] }，才能达到等式左边才表示i,而等式右边表示i-1的效果。
代码
public static int solve(int n ,int w, int[] weight, int[] value){ //动态规划结果数组 int[] dp=new int[w+1]; //最优值dp[j]=max{dp[j], dp[j-w[i]]+vi} , 其中0<=j<=w; for(int i=0;i<n;i++){ for(int j=w;j>=weight[i];j--){ if(dp[j-weight[i]]+value[i]>dp[j]){ dp[j]=dp[j-weight[i]]+value[i]; } } } return dp[w]; }参考: http://blog.csdn.net/sj13051180/article/details/6687674
新闻热点
疑难解答
