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
#include <iostream>
using namespace std;

int main(){
	
	int a[4][2] = {{2,3}, {3,4}, {5,6}, {6,8}};			//存放物品容量和价值的数组 
	int b[5][11];										//用于动态规划的数组
	
	int i, j;
	int curValue;
	
	for (i=0; i<5; i++) {
		
		for (j=0; j<11; j++) {
			
			if (i==0) {									//不装任何编号的物品，当然最大价值也为0 
				b[i][j] = 0;
			}
			
			else{
				
				if (a[i-1][0]>j) {						//装不下当前编号的东西 
					b[i][j]=b[i-1][j];					//包括当前编号（i以内）的最大价值与不包括当前编号(只包括i-1以内)的最大价值相同 
				}
				
				else{									//装的下当前编号的东西 
				
					curValue = a[i-1][1] + b[i-1][j- a[i-1][0] ];		//当前最大价值（可能性1） = 包括当前编号物品的价值 + 去除当前编号容量后的最大价值 
					
					if (curValue>b[i-1][j]) {							//如果可能性1>不包括当前编号的最大价值（可能性2） 
						b[i][j] = curValue;								//当前最大价值 取可能性1与可能性2的最大值（可能性1） 
					}
					else {												//如果可能性1<不包括当前编号的最大价值（可能性2）
						b[i][j] = b[i-1][j];							//当前最大价值 取可能性1与可能性2的最大值（可能性2） 
					}
					
				} 
			
			}
			
			
			cout << b[i][j] << "t";									//输出最大价值矩阵 
			
		}
		
		cout << endl;
	} 
	
	return 0;
}

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
#include <iostream>
using namespace std;

int main(){
	
	int a[4][2] = {{2,3}, {3,4}, {5,6}, {6,8}};			//存放物品容量和价值的数组 
	int b[5][11];										//用于动态规划的数组
	
	int i, j;
	int curValue;
	
	for (i=0; i<5; i++) {
		
		for (j=0; j<11; j++) {
			
			if (i==0) {									//不装任何编号的物品，当然最大价值也为0 
				b[i][j] = 0;
			}
			
			else{
				
				if (a[i-1][0]>j) {						//装不下当前编号的东西 
					b[i][j]=b[i-1][j];					//包括当前编号（i以内）的最大价值与不包括当前编号(只包括i-1以内)的最大价值相同 
				}
				
				else{									//装的下当前编号的东西 
				
					curValue = a[i-1][1] + b[i-1][j- a[i-1][0] ];		//当前最大价值（可能性1） = 包括当前编号物品的价值 + 去除当前编号容量后的最大价值 
					
					if (curValue>b[i-1][j]) {							//如果可能性1>不包括当前编号的最大价值（可能性2） 
						b[i][j] = curValue;								//当前最大价值 取可能性1与可能性2的最大值（可能性1） 
					}
					else {												//如果可能性1<不包括当前编号的最大价值（可能性2）
						b[i][j] = b[i-1][j];							//当前最大价值 取可能性1与可能性2的最大值（可能性2） 
					}
					
				} 
			
			}
			
			
			cout << b[i][j] << "t";									//输出最大价值矩阵 	
		}	
		cout << endl;
	}
	
	cout << "最大价值为：" << b[4][10] <<endl;
	
	

	//运用回溯法，求解最大价值物品编号集合
	i=4;
	j=10;

	while (j>0) {														//当容量>0时，持续回溯
	
		if (b[i][j]==b[i-1][j]) {			//如果包含编号（i以内）的最大价值与不包含（i-1以内）一致
			i--;							//说明该编号未在最大价值编号集合中，i自减
		}
		
		else {
			cout << "编号" << i << "在最大价值集合中" << endl;
			j -= a[i-1][0];					//否则，减去该编号的容量
			i--;
		}
	}
	
	return 0;
}