问题描述

有N件物品和一个容积为M的背包。第i件物品的体积
w[i],价值是d[i]。求解将哪些物品装入背包可使价值总
和最大。每种物品只有一件,可以选择放或者不放
(N<=3500,M <= 13000

思路

用 F[i][j] 表示取前i种物品,使它们总体积不超过j的最优
取法取得的价值总和。要求F[N][M]
边界:if (w[1] <= j)
F[1][j] = d[1];
else
F[1][j] = 0;

递推: F[i][j] = max(F[i-1][j],F[i-1][j-w[i]]+d[i])
取或不取第 i种物品,两者选优
(j-w[i] >= 0才有第二项)

本题如用记忆型递归,需要一个很大的二维数组,会
超内存。注意到这个二维数组的下一行的值,只用到了
上一行的正上方及左边的值,因此可用滚动数组的思想
,只要一行即可。即可以用一维数组,用“人人为我”
递推型动归实现

中心代码
int knapSack(int w[],int v[],int C) { int size = w.length; if (size == 0) {
return 0; } int dp[][] = new int[size][C + 1]; //初始化第一行 //仅考虑容量为C的背包放第0个物品的情况
for (int i = 0; i <= C; i++) { dp[0][i] = w[0] <= i ? v[0] : 0; } //填充其他行和列 for
(int i = 1; i < size; i++) { for (int j = 0; j <= C; j++) { dp[i][j] = dp[i - 1]
[j]; if (w[i] <= j) { dp[i][j] = max(dp[i][j], v[i] + dp[i - 1][j - w[i]]); } }
} return dp[size - 1][C]; }

技术
©2019-2020 Toolsou All rights reserved,
一个名叫“讨火车”的小村子 终于把火车讨来了运营商 网站访客手机号码抓取hive压缩&&hdfs合并小文件精准手机号抓取,运营商大数据函数基本定义和使用‘未完待续Spring Boot教程十六:SpringBoot注入类实现多线程基于神经网络的车辆牌照字符识别技术MyBatis 新增数据 成功 返回 自增主键ID值json反斜杠问题接错水管喝了三年软水?软水和软水机究竟有何用