- it技术
- 十八、程序员10大算法之动态规划
一、动态规划算法介绍
二、代码实现
import javax
.swing
.plaf
.metal
.MetalIconFactory
;
public class KnapsackProblem {
public static void main(String
[] args
) {
int[] w
= {1,4,3};
int[] val
= {1500,3000,2000};
int m
= 4;
int n
= val
.length
;
int[][] v
= new int[n
+1][m
+ 1];
int[][] path
= new int[n
+1][m
+1];
for (int i
= 0; i
< v
.length
; i
++) {
for (int j
= 0; j
< v
[0].length
; j
++) {
v
[i
][0] = v
[0][j
] = 0;
}
}
for (int i
= 1; i
< v
.length
; i
++) {
for (int j
= 1; j
< v
[0].length
; j
++) {
if(w
[i
-1] > j
){
v
[i
][j
] = v
[i
-1][j
];
}else{
v
[i
][j
] = Math
.max(v
[i
-1][j
],val
[i
-1]+v
[i
-1][j
-w
[i
-1]]);
if(v
[i
-1][j
] < val
[i
-1]+v
[i
-1][j
-w
[i
-1]] ){
v
[i
][j
] = val
[i
-1]+v
[i
-1][j
-w
[i
-1]];
path
[i
][j
] = 1;
}else{
v
[i
][j
] = v
[i
-1][j
];
}
}
}
}
System
.out
.println("动态规划处理后的v[i][j]:");
for (int i
= 0; i
< v
.length
; i
++) {
for (int j
= 0; j
< v
[0].length
; j
++) {
System
.out
.print(v
[i
][j
] + " ");
}
System
.out
.println();
}
System
.out
.println("能够放入背包中的物品表示数组为：");
for (int i
= 0; i
< path
.length
; i
++) {
for (int j
= 0; j
< path
[0].length
; j
++) {
System
.out
.print(path
[i
][j
] + " ");
}
System
.out
.println();
}
System
.out
.println("最后的解为：");
int i
= path
.length
- 1;
int j
= path
[0].length
- 1;
while(i
> 0){
if(path
[i
][j
] == 1){
System
.out
.printf("第%d个商品放入到背包\n",i
);
j
-= w
[i
-1];
}
i
--;
}
}
}
三、测试结果
动态规划处理后的v
[i
][j
]:
0 0 0 0 0
0 1500 1500 1500 1500
0 1500 1500 1500 3000
0 1500 1500 2000 3500
能够放入背包中的物品表示数组为：
0 0 0 0 0
0 1 1 1 1
0 0 0 0 1
0 0 0 1 1
最后的解为：
第
3个商品放入到背包
第
1个商品放入到背包
