The title

1. Integer transformation problem

The two transformations of the integer I are defined as, (round down); An algorithm is designed to find two integers a and B, and transform integer A into integer B by the sum transformation of the least number. For example, the implementation hint: by observing f and g, f always makes I bigger and g always makes I smaller. Therefore, we can determine the size relationship between I and the target value m before deciding which operation x should perform. If x>m, let it perform g; Otherwise, perform f. The solution of the problem is divided into two cases, one is there is a solution, that is, n can be transformed into m by the function; The other is no solution, that is, n cannot be transformed into m by the function. It’s easier if you have a solution, you just have to figure out if the final I is equal to m. If I is equal to m, then n has been transformed to m, recursively. The case of no solution can be analyzed by the following example. Let’s say our input n is equal to 9 and m is equal to 5.

N > m, g, n = (9/2) = 4 n < m, f, n = 3 _4 = 12 n > m, g, n = [12/2] n > = 6 m, f, n = [6/2] = 3 n < m, g, n = 3 _3 = 9 n > m, f, n = (9/2) = 4

If the value of n is trapped in a repeating loop, if the elements that we calculated are present in the recursion, then n cannot be converted to m. The implementation of this method is slightly more complicated, requiring the determination of whether the current value has occurred before. Another simple approach: for the case where M cannot be changed to N, a judgment condition can be added, such as until the depth reaches a large value (e.g., 1000). Backtracking method is implemented by subset tree, and the subset tree structure is:

There are two backtracking conditions, one is that I is equal to m, and the other is that repeated numbers occur. The second return condition can be determined using a function, test.

Pruning conditions:

Explicit constraint: if x>m, cut its left subtree; If x

#include <iostream> using namespace std; int fn[1001]; int arr[1001]; int cnt = 0; int test(int n) { for(int i=0; i<cnt-1; i++) if(arr[i]==n)return 0; return 1; } void display(int n,int m) { cout<<m<<"="; for(int i=cnt-1; i>=0; i--) if(fn[i]==1)cout<<"g"; else cout<<"f"; cout<<"("<<n<<")"<<endl; } void dfs(int n,int m,int num) { if(n==m) { display(num,m); return ; } else { if(n>m){n=n/2; fn[cnt]=1; } else n=n*3; arr[cnt++]=n; if(test(n)&&cnt<1000)dfs(n,m,num); Else {cout<<" no solution "<<endl; return; } } } int main() { int n,m; cin>>n>>m; dfs(n,m,n); return 0; }Copy the code

2. Subset sum problem

Problem description: Given the set S, S has n positive integers, M is a positive integer. The subset sum problem determines whether there exists a subset S1 of S such that the sum of the elements in S1 is equal to M. Please design backtracking method to solve the subset sum problem. If there is No Solution to the problem, output “No Solution”; if there is a Solution to the problem, output the value of each element in the subset S1.

#include <iostream> using namespace std; int arr[1001]; int dp[1001]; int sum=0; int cnt=0; void dfs(int n,int m,int k) { if(sum>m||k>n)return; if(sum==m) { cnt++; for(int i=0; i<n; i++) if(dp[i])cout<<arr[i]<<" "; cout<<"\n"; } else for(int i=0; i<2; i++) if(i==0){ sum+=arr[k]; dp[k]=1; dfs(n,m,k+1); dp[k]=0; sum-=arr[k]; } else dfs(n,m,k+1); } int main() { int n,m; cin>>n>>m; for(int i=0; i<n; i++) { cin>>arr[i]; } dfs(n,m,0); if(cnt==0)cout<<"No Solution"<<endl; return 0; }Copy the code

3. Work distribution.

Problem description: There are n jobs assigned to N people. The cost of assigning job I to person J is CIJ. Please design an algorithm to assign one different job to each person and minimize the total cost. Implementation tip: the solution space of this problem is a permutation tree, which can be realized by the backtracking framework of search permutation tree.

#include <iostream> using namespace std; int arr[22][22]; int minCost = 9999; int sumCost = 0; int vis[22]; void dfs(int k,int n) { if(k==n) { if(sumCost<minCost)minCost=sumCost; } else { for(int i=0; i<n; i++) { sumCost+=arr[k][i]; if(vis[i]! =1&&sumCost<minCost) { vis[i]=1; dfs(k+1,n); vis[i]=0; } sumCost-=arr[k][i]; } } } int main() { int n; cin>>n; for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin>>arr[i][j]; dfs(0,n); cout<<minCost<<endl; return 0; }Copy the code

This article uses the article synchronization assistant to synchronize