-
Notifications
You must be signed in to change notification settings - Fork 27
/
Copy path624.go
45 lines (40 loc) · 787 Bytes
/
624.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// UVa 624 - CD
package main
import (
"fmt"
"os"
)
func knapsack(n int, tracks []int) (int, []int) {
dp := make([]int, n+1)
path := make([][]int, n+1)
for i, vi := range tracks {
for j := n; j >= vi; j-- {
if dp[j] < dp[j-vi]+vi {
dp[j] = dp[j-vi] + vi
path[j] = append(path[j-vi], i)
}
}
}
return dp[n], path[n]
}
func main() {
in, _ := os.Open("624.in")
defer in.Close()
out, _ := os.Create("624.out")
defer out.Close()
var n, t int
for {
if _, err := fmt.Fscanf(in, "%d%d", &n, &t); err != nil {
break
}
tracks := make([]int, t)
for i := range tracks {
fmt.Fscanf(in, "%d", &tracks[i])
}
max, path := knapsack(n, tracks)
for _, vi := range path {
fmt.Fprint(out, tracks[vi], " ")
}
fmt.Fprintf(out, "sum:%d\n", max)
}
}