6126：

subject ：

There is a salesperson from the city 1 set out , To the city 2,3,…,n To sell goods , Finally back to the city 1. Any two cities i,j Distance between dij(dij=dji) Is known , Ask him what route he should follow , To make the shortest route ?

input ：

The first 1 Number of row cities n

From the first 2 Enter the matrix of the distance between any two cities at the beginning of the line , The distance between two cities without roads is -1

output :

The first 1 that 's ok ： Shortest distance

The first 2 that 's ok ： City order

Input / output instance ：

input ：

4      // Number of cities

-1 30 6 4         // Distance matrix between cities

30 -1 5 10

6 5 -1 20

4 10 20 -1

output ：

25    // Shortest distance

1 3 2 4    //

Thinking is in the code snippet
#include <iostream> using namespace std; const int N = 10; int g[N][N], x[N];
int best[N], ans, cost; // best[] record final Shortest route ,ans Minimum distance value // x[] record stay dfs In process
Possible route ,cost Corresponding route Distance value int n; void dfs(int t) { if (t > n) // Reach leaf node { if
(g[x[t - 1]] > 0 && cost + g[x[t - 1]] < ans) { ans = cost + g[x[t -
1]]; for (int i = 1; i <= n; i++) best[i] = x[i]; } return; } else { for
(int i = t; i <= n; i++) { if (g[x[t - 1]][x[i]] > 0 && g[x[t - 1]][x[i]] +
cost < ans) { cost += g[x[t - 1]][x[i]]; swap(x[t], x[i]);
// Save the second time you want to go t City to x[t] in , Namely x[i] For going The first t Cities // First city dfs(t + 1); // Search for next city // to flash back cost -=
g[x[t - 1]][x[t]]; swap(x[t], x[i]); } } } } int main() { cin >> n; for (int i
= 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> g[i][j]; } ans = 10000;
// Infinite number cost = 0; for (int i = 1; i <= n; i++) { x[i] = i; } dfs(2); cout << ans
<< endl; for (int i = 1; i <= n; i++) { cout << best[i] << " "; } return 0; }
6125：

subject ：

have n Items and a capacity of c My backpack . The first i What is the value of this item v[i], Weight is w[i]. Find out which items are loaded into the backpack to maximize the total value . so-called 01 knapsack , Indicates that there is only one item per item , Either load , Or don't load .

input ：

The first 1 Line is the backpack capacity

The first 2 Number of line items n

The first 3 that 's ok ：n Weight of items

The first 4 that 's ok ：n Value of an item

output ：

The first 1 that 's ok ： optimal value

The first 2 that 's ok ： Optimal solution

Input / output example ：

input ：

50   // Backpack Capacity

4   // Number of items

30 20 40 10    // Article weight

10 20 30 40    // Value of goods

output ：

70    // optimal value

0 0 1 1    // Optimal solution

understand ： Understanding of subset tree

#include<iostream> using namespace std; int n, t;//n Is the number of items double C;// Backpack Capacity
double w;// weight double v;// value double p;// Unit value of goods int
BestX;// The most appropriate serial number is 1 Inappropriate for 0 int X;// The most appropriate serial number at this stage int
order;// Record the serial number knapsack Had an exchange when double CurWeight = 0.0;// Weight of backpack items at this stage
double CurValue = 0.0;// Value of backpack items at this stage double BestValue = 0.0;// Maximum value of backpack items void
knapsack()// Sort items by value per unit weight ; { int temporder = 0; double temp = 0.0; for (int i =
1; i <= n; i++) p[i] = v[i] / w[i];// Value of goods / Article weight for (int i = 1; i <= n - 1; i++)
{ for (int j = i + 1; j <= n; j++) if (p[i] < p[j]) { temp = p[i]; p[i] = p[j];
p[j] = temp; temporder = order[i]; order[i] = order[j]; order[j] = temporder;
temp = v[i]; v[i] = v[j]; v[j] = temp; temp = w[i]; w[i] = w[j]; w[j] = temp; }
}// Sort items by value per unit weight ; } int bound(int t) { int cleft = C - CurWeight;// Residual capacity int b =
CurValue;// Value of items in backpack at present while (t <= n && w[t] <= cleft)// Load items with decreasing weight value { cleft =
cleft - w[t]; b = b + v[t]; t++; } if (t <= n)// Full backpack b = b + v[t] * cleft /
w[t];// calculation t The unit value of item No. fills the remaining space return b; } void backtrack(int t) { if (t >
n)// Reached the leaf node { if (CurValue > BestValue)// It's been searched once , Assign an existing maximum value ; { BestValue =
CurValue; for (int i = 1; i <= n; i++) BestX[i] = X[i]; } return; } if
(CurWeight + w[t] <= C)// Less than the maximum capacity of the backpack, enter the left subtree { X[t] = 1;// Whether the record is loaded CurWeight += w[t];
CurValue += v[t]; backtrack(t + 1);// to flash back CurWeight -= w[t]; CurValue -= v[t]; }
if (bound(t + 1) > BestValue)// Enter right subtree { X[t] = 0;// He doesn't have anything suitable for him backtrack(t +
1);// judge } } int main() { cin >> C >> n; // Backpack Capacity and number of items for (int i = 1; i <= n;
i++)// It all started from the beginning { cin >> w[i]; // Article weight order[i] = i;// Meaning of serial number } for (int i = 1; i
<= n; i++) cin >> v[i];// Value of goods knapsack(); backtrack(1); cout<<BestValue<<endl;
for (int i = 1; i <= n - 1; i++) { for (int j = 1; j <= n - 1; j++) { if
(order[j] > order[j + 1]) { t = order[j]; order[j] = order[j + 1]; order[j + 1]
= t; t = BestX[j]; BestX[j] = BestX[j + 1]; BestX[j + 1] = t; } }
}// He asked to output the original serial number for (int i = 1; i <= n; i++) cout<<BestX[i]; return 0; }

Technology
Daily Recommendation