2

A[1] から A[N] までの N 個の整数が与えられます。.になるように、これらの整数に重みを割り当てる必要がありますweighted sum is maximized。重みは次の条件を満たす必要があります。

  1. 各重みは正の整数でなければなりません。
  2. W[1] = 1
  3. i > 1 の場合、W[i] は [2, W[i-1] + 1] の範囲にある必要があります。

加重合計は次のように定義されます S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]

例:

n=4 , array[]={ 1 2 3 -4 } , answer = 6 when we assign { 1 2 3 2 } respective weights .

したがって、私の理解と調査によると、Greed の解決策はありません。私はペンと紙で多くのテストケースを作成しましたが、貪欲な戦略を得ることができませんでした。

あらゆるアイデア/ヒント/人々へのアプローチ。

4

3 に答える 3

1

に重みを割り当てることによってdp[i][j]作成できる最大の重み付き合計を等しくします。明らかに。状態があり、各状態ごとに繰り返しがかかるため、全体の時間の複雑さは になります。それを減らすために、再発にかなりの重複があることに気付くことができます。A[1..i]jA[i]dp[i][j] = j*A[i] + max(dp[i - 1][(j - 1)..N])O(N^2)O(N)O(N^3)O(N^2)

ならdp[i][j] = j * A[i] + max(dp[i - 1][(j - 1)..N])、

dp[i][j - 1] = (j - 1)*A[i] + max(dp[i - 1][(j - 2)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i - 1][(j - 1)..N]) = (j - 1)*A[i] + max(dp[i - 1][j - 2], dp[i][j] - j*A[i])

つまり、再帰の計算には O(1) しかかからず、全体で O(N^2) 時間かかります。

于 2013-08-15T20:35:07.790 に答える
0

これは、あなたまたは他の誰かが非常に迅速な解決策を思い付くのに役立つかもしれない小さな洞察です. 最適なソリューションを得るには、各ステップで前の重みから +1 ずつ重みを増やすか、最小の 2 まで重みを減らすかのいずれかであると安全に想定できることに注意してください。これを確認するには、プロパティに違反する最適解。次に、ある位置で 2 をi-1超える重みがあり、次の重みもその位置で 2 を超えますiが、増加しません。ここで、position から始まる最適解の重みのサブシーケンスを弱く増加させる最大長を考えます。i(弱い増加とは、サブシーケンスの各ステップで重みが減少しないことを意味します)。仮定により、このサブシーケンスの最適解は、すべての重みから 1 を引いたサブシーケンスを除いて、同じ解より悪くはありません。しかし、これは、サブシーケンスのすべての重みを 1 増やしても、最適解が悪化しないことを意味します。したがって、最適なソリューションを得るには、各ステップで、重みを 1 増やすか、重みを最小の 2 に設定することを安全に想定できます。

于 2013-08-15T21:06:25.897 に答える
0

この問題を O(N³) 時間で解決するには、かなり標準的な動的計画法を使用できます。V(k,u) は、Wₖ₋₁ の値が u のときに要素 k...N を使用して取得できる最良の値を示します。V(k,u) は、g の範囲が 2 から u+1 のときの g·Aₖ+V(k-1,g) の最大値であり、V(N,u) は (u+1)· A Nが正の場合は A N、それ以外の場合は 2·A N。

V(k,u) の計算では、u は高々 k であるため、(k,u) の可能な値は N*(N-1)/2 あるため、概説した方法では O(N²) 空間を使用し、 O(N³)時間。

于 2013-08-15T20:03:43.897 に答える