lavos/cap4/ex25.go

package cap4

// Ex25 项目资源分配，项目数，资源数，收益表（第i个项目可得到的利润）
func Ex25(m, n int, income []float64) ([]int, float64) {
	dp := make([]float64, n)
	tmp := make([]float64, n)

	a := _makeMatrix(m, n)

	for i := 0; i < n; i++ {
		a[0][i] = i
	}

	copy(dp, income)
	copy(tmp, income)

	// 前i个项目
	for i := 1; i < m; i++ {
		// 资源数限制在j时
		for j := 0; j < n; j++ {
			// 第i个项目可分配k个资源
			for k := 0; k < j; k++ {
				if dp[j-k]+income[k] > tmp[j] {
					tmp[j] = dp[j-k] + income[k]
					a[i][j] = k
				}
			}
		}

		copy(dp, tmp)
	}

	rest := n
	gain := make([]int, m+1)
	for i := m - 1; i > 0; i-- {
		gain[i] = a[i][rest]
		rest -= gain[i]
	}

	return gain, dp[n]
}