9.3 multistage decision making problem

This chapter looks at the problem first.

9.3.1 shortest path of multi segment diagram

9-4 unidirectional TSP (UVA 116)

For an integer matrix with M rows and N columns (m < = 10, n < = 100, the data range here is to remind you that this is a matrix whose width may be much greater than its length), start from any position in the first column, choose one direction to the right, upper right or lower right each time, and finally reach the last column. Minimum sum of integers required. The whole matrix is circular, that is, the previous row of the first row is the last row, and the next row of the last row is the first row. The row number of each column of the output path, and the smallest one is output in case of multiple solutions.

Analysis: the design of state is relatively simple. d(i,j) represents the minimum overhead from grid (i,j) to the last column. So there is a state transition equation: d[i][j]=max{d[i-1][j+1],d[i][j+1],d[i+1][j+1]}+a[i][j]. The boundary conditions are relatively simple: d[i][n]=0, d[i][n-1]=a[i][j], which can be deduced inversely.

The code is as follows:

int ans=INF,first=0;//ans means the shortest path, and first means the shortest path can be obtained from the first row of the first column 
for (int j=n-1;j>=0;j--) for (int i=0;i<m;i++){
	if (j==n-1) d[i][j]=a[i][j];//boundary condition  
	else{ int rows[3]={i-1,i,i+1};//It represents three directions: top right, right and bottom right 
		//Ring matrix, the upper row of row 0 is row m-1, and the lower row of row m-1 is row 0 
		if (i==0) rows[0]=m-1; if (i==m-1) rows[2]=0; 
		sort(rows,rows+3); d[i][j]=INF;//The sorting here is to facilitate the solution with the smallest dictionary order 
		for (int k=0;k<3;k++){ if (d[rows[k]][j+1]<d[i][j])
			{d[i][j]=d[rows[k]][j+1]; next[i][j]=rows[k]}
			//Because the values of n and m are small, we choose to use the next array to store the path 
		}	
	} 
	if (j==0&&d[i][j]<ans){ans=d[i][j]; first=i;} 
} printf("%d" first+1);//Output the starting point of the first column
//Similar to the operation of array analog pointer, find the next element through the next array 
for (int i=next[first][0],j=1;j<n;i=next[i][j],j++) printf("% d",i+1); 

9.3.2 0-1 knapsack problem

Knapsack problem with unlimited items

There are n kinds of items, each of which has an infinite number. The volume of article i is Vi and the weight (value) is Wi. Select some items and put them into a backpack with a capacity of C. yes, the weight of the items in the backpack should be as large as possible on the premise that the total volume does not exceed C.

Analysis: in the previous coin problem, it is required to select as many coins as possible, which is equivalent to that in the knapsack problem with unlimited items here, the weight (value) Wi is set to 1. Conversely, you only need to change + 1 of the code there to + Wi. The code is roughly as follows:

maxv[0]=0;//Represents the path length of the longest path respectively
for (int i=1;i<=C;i++) maxw[i]=-INF;
for (int i=1;i<=C;i++) for (int j=1;j<=n;j++) if (i>=v[j]){
	//i represents the state node and j represents the j-th volume (state transition equation)
	maxw[i]=max(maxw[i],maxw[i-v[j]]+W[i]);
}//Output maxw[C] 
void print_ans(int *d,int C){///The d array of the call here is maxw
	for (int i=1;i<=n;i++) if (C>=v[i]&&d[C]==d[C-v[i]]+W[i]){
		printf("%d ",i); print_ans(C-v[i]); break;
	}
} 

0-1 knapsack problem

The condition is basically the same as that of unlimited items. The only difference is that there is only one item of each kind at most.

Analysis: the original method is not applicable here, because according to the original method, we cannot determine whether an object has been taken in the current state (if an array is used to record, the time will be too long, and the advantages of dynamic programming will not be reflected).

Therefore, consider adding an attribute to the state. d(i,j) represents the maximum weight of the first I items in the backpack with capacity j, and the answer is d[n][C]. Then there is d(i,j)=max(d(i-1,j),d(i-1,j-V[i])+W[i]). The boundary condition is 0 when i=0 and negative infinity when j < 0 (I think it's better to eliminate it directly). The code is as follows:

for (int i=0;i<=n;i++) for (int j=0;j<=C;j++){
	d[i][j]=(i==0)?0:f[i-1][j];
	if (j>=V[i]) f[i][j]=max(f[i][j],f[i-1][j-V[i]]+W[i]);
}

The advantage of this method over the back-to-back recursive method is that it can be input and processed at the same time without saving the data:

for (int i=1;i<=n;i++){scanf("%d%d",&V,&W);
	for (int j=0;j<=C;j++){
		d[i][j]=(i==1)?0:f[i-1][j];
		if (j>=V) f[i][j]=max(f[i][j],f[i-1][j-V]+W);
	}
}

The book also provides a method to scroll the array:

memset(f,0,sizeof(f))
for (int i=1;i<=n;i++){scanf("%d%d",&V,&W);
	for (int j=C;j>=0;j--) if (j>=V) f[j]=max(f[j],f[j-V]+W);
}

This method highlights a paradox. In fact, for i=x, f[j]=max(f[j],f[j-V]+W) is equivalent to f[x][j]=max(f[x][j],f[x-1][j-V[x]+W[x]). For f[j-V] (note that the inner loop of the code scrolling the array is traversed in reverse order from back to front, so f[j-V] will traverse later relative to f[j], so f[j-V] retains the value obtained for the previous loop, that is, f[x-1][j-V[x]).

However, it should be noted that this method is difficult to print the scheme (because it has been overwritten).

There is another example in theory, but the analysis seems to be a simple 0-1 backpack problem, so I won't introduce it more (in fact, it's not because it's simple, but because I haven't been to ktv to sing, and I haven't heard Gu Juji's song = =).