动态规划之01背包 数组模拟商品(Java)

1
2
3
4
动态规划:先解决子问题,然后逐步解决大问题
思路:通过画二维表格填充价值实现
核心公式: 当前的价值 = (上一个单元格的价值,当前商品的价值+剩余空间的最大值)
能够解决的问题:要么拿。要么不拿
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
/**
* @author cheene
* @since 2018年1月23日
* 该题目假设: 音响 3000元 4kg 笔记本电脑 2000元 3kg 吉他 1500元 1kg iphone 2000元 1kg
* 背包的重量是 4kg 求拿什么东西使其价值最大
* **/
public class dp01package02ByArray {
public static void main(String[] args) {
String []name = {"音响","笔记本电脑","吉他","iphone"};//额这一行貌似没有用到。
//仅是输出了最大价值没有输出组成该最大价值的解
int [] value = {3000,2000,1500,2000};
int [] weight = {4,3,1,1};
int dp[][] = new int[5][5];
for(int i = 1; i < dp.length; i++){// i 代表着是第几个商品; j 代表着是 当前的重量
for(int j = 1; j < dp.length; j++){
if(i == 1){// 开始填充第一行
if(j-1 == weight[i-1])//判断当前的商品的重量是不是与此时背包的重量相等
dp[i][j] = value[i];
if(j != 0 && dp[i][j-1] != 0){//当前面不为零的时候
dp[i][j] = dp[i][j-1];
}
}else{
if(j - weight[i-1] > 0){// 判断当前的背包的重量能不能装下该产品
dp[i][j] = Math.max(dp[i-1][j],value[i-1] + dp[i-1][j-weight[i-1]]);
}else if(j == weight[i-1]){
dp[i][j] = Math.max(dp[i-1][j], value[i-1]);
}
}
}
}
for(int i = 1; i < dp.length; i++){
for(int j = 1; j < dp.length ; j++){
System.out.print(dp[i][j] +"\t");
}
System.out.println();
}
}
}
1
2
3
4
5
6
7
8
9
10
/**
* 最后的打印的结果:
----------------------------------------
0 0 0 0
0 0 2000 2000
1500 1500 2000 3500
2000 3500 3500 4000
----------------------------------------
*
* ***/