动态规划之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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import java.util.ArrayList;
/**
* @author cheene
* @since 2018年1月23日
* 0-1 背包问题
* 该题目假设: 音响 3000元 4kg 笔记本电脑 2000元 3kg 吉他 1500元 1kg iphone 2000元 1kg
* 背包的重量是 4kg 求拿什么东西使其价值最大
*
* **/
public class dp01packageByClass {
public static void main(String[] args) {
//生成商品
Good sound = new Good("音响",3000,4);
Good noteComputer = new Good("笔记本电脑",2000,3);
Good guiter = new Good("吉他",1500,1);
Good iphone = new Good("iphone",2000,1);
Goods goods = new Goods();
goods.addGood(sound);
goods.addGood(noteComputer);
goods.addGood(guiter);
goods.addGood(iphone);
//使用一个二维网格来填充
int N = goods.getGoods().size();
int result [][] = new int[N+1][N+1];
// i 代表着第 i 件商品; j 代表着 第 i 行的重量
Good temp;
for(int i = 1; i < N+1; i++){
temp = goods.getGoods().get(i-1);
for(int j = 1; j < N+1; j++){
if(i == 1){//第一次只有一件商品
if(j == temp.getWeight()){
result[i][j] = temp.getValue();
}
if(j != 1 && result[i][j-1] != 0){
result[i][j] = result[i][j-1];
}
}
else{//从第二行开始
if(j - temp.getWeight() > 0){
result[i][j] = Math.max(result[i-1][j],temp.getValue() + result[i-1][j-temp.getWeight()]);
}else if(j - temp.getWeight() == 0){
result[i][j] = Math.max(result[i-1][j],temp.getValue());
}
}
}
}
//输出一下看看
for(int i = 1; i < N+1;i++){
for(int j = 1; j < N+1; j++){
System.out.print(result[i][j] + "\t");
}
System.out.println();
}
}
}
/**
* Good 用来存储每个商品的详细情况
* @param name 商品名
* @param value 商品价值
* @param weight 商品重量
*
* **/
class Good{
private String name;
private int value;
private int weight;
Good(String name,int value,int weight){
this.name = name;
this.value = value;
this.weight = weight;
}
public String toString(){
return "名称 : "+ this.name + "价值: " + this.value + " 重量: " + this.weight;
}
public String getName() {
return name;
}
public int getValue() {
return value;
}
public int getWeight() {
return weight;
}
}
/**
* 将所有的商品存储在里面
* **/
class Goods{
private ArrayList<Good> list ;
Goods(){
list = new ArrayList<Good>();
}
public void addGood(Good good){
list.add(good);
}
public ArrayList<Good> getGoods(){
return list;
}
}
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
----------------------------------------
*
* ***/