1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| val maxWeight = 4
val nameArray = arrayListOf<String>("吉他","音响","电脑","手机","MP3")
val weightArray = arrayListOf<Int>(1,4,3,1,1)
val costArray = arrayListOf<Int>(1500,3000,2000,2000,1000)
backPackSolution(maxWeight,weightArray,costArray,nameArray)
private fun backPackSolution(maxWeight:Int,weights:ArrayList<Int>,costs:ArrayList<Int>,nameArray:ArrayList<String>){
val n = weights.size
val resultArray = Array(n+1){IntArray(maxWeight+1)}
var mapResultName = mutableMapOf<String,String>()
for (i in 0..maxWeight){
resultArray[0][i] = 0
mapResultName["0"+i.toString()] = ""
}
for (i in 0..n){
resultArray[i][0] = 0
mapResultName[i.toString()+"0"] = ""
}
for (i in 1..n){
for (j in 1..maxWeight){
resultArray[i][j] = resultArray[i-1][j]
mapResultName[i.toString()+j.toString()] = mapResultName[(i-1).toString()+j.toString()] ?: ""
val k = j - weights[i-1]
if ( k< 0 ){
continue
}
if (resultArray[i-1][j - weights[i-1]] + costs[i-1] > resultArray[i-1][j]){
resultArray[i][j] = resultArray[i-1][j - weights[i-1]] + costs[i-1]
mapResultName[i.toString()+j.toString()] = mapResultName[(i-1).toString()+(j - weights[i-1]).toString()] +" "+ nameArray[i-1]
}
}
}
println("最优价格："+resultArray[n][maxWeight])
println("最优名称："+mapResultName[n.toString()+maxWeight.toString()]?.trim())
}
|
