RikkawithBook

There are n books on Rikka's desk. The length, width, height and weight of the i-th book are $l_i$ , 1, 1 and $w_i$ respectively. We call the two sides of length $l_i$ as long sides, and two sides of length 1 as short sides. For each book, the mass is evenly distributed in its volume.
Today, Rikka wants to stack these books on her desk. Rikka plans to do it in n turns: In each turn, she will select out one book among all remaining books, and stack it directly above the previous book (The first book will be put directly on the desk).
For tidiness, Rikka make the following four requirement:

The left long sides of all books must be coplaner. So do the right long sides;
The plane containing all left long sides must be vertical to the ground. So do the right long sides;
All short sides of all books must be parallel to the border of the desk;
The book stack must be stable. Falling thick books are dangerous!

Informally, the books will be stacked as the following figure:

For fun, Rikka wants to make the book stack looking as strange as possible. For each book, Rikka defines its strangeness as the horizontal distance for its front short edge to be outside the desk. The strangeness of the whole book stack is defined as the maximum strangeness of books. For example, in the previous figure, the strangeness of the book stack is equal to the length of segment TU.
Rikka wants you to come up with a stacking plan so that the strangeness of the book stack is as large as possible.
More assumptions:

Suppose the gravity coefficient is fixed. It will not change when the height change;
Suppose the shape of the desk and books would never change.

The first line contains a single integer $n\ (1 \leq n \leq 20)$ , the number of books.
The second line contains n integers $l_i\ (1 \leq l_i \leq 10^3)$ , representing the length of each book.
The third line contains n integers $w_i\ (1 \leq w_i \leq 10^3)$ , representing the weight of each book.

n = int(input()) l = list(map(float, input().split())) w = list(map(float, input().split())) sum_w = [0] * (1 << n) for s in range(1, 1 << n): for i in range(n): if s >> i & 1: sum_w[s] = sum_w[s ^ (1 << i)] + w[i] break f = [0] * (1 << n) for s in range(1, 1 << n): for i in range(n): if s >> i & 1: t = s ^ (1 << i) f[s] = max(f[s], f[t] + w[i] / sum_w[s] * l[i] / 2) f[s] = max(f[s], l[i] * (1 - w[i] / sum_w[s] / 2)) print(f[-1])

#include<bits/stdc++.h> using namespace std; typedef double db; db dp[1<<20],v[20],l[20]; int n; int main(){ cin >> n; for (int i=0;i<n;i++) cin >> l[i]; for (int i=0;i<n;i++) cin >> v[i]; for (int i=1;i<(1<<n);i++){ db w=0; for (int j=0;j<n;j++) if (i&(1<<j)) w+=v[j]; for (int j=0;j<n;j++) if (i&(1<<j)){ dp[i]=max(dp[i],dp[i^(1<<j)]+v[j]/w*l[j]/2); dp[i]=max(dp[i],l[j]-v[j]/w*l[j]/2); } } printf("%.10f\n",dp[(1<<n)-1]); return 0; }

详情