hello-algo/codes/swift/chapter_dynamic_programming/knapsack.swift
nuomi1 7359a7cb4b
Review Swift codes (#1150)
* feat(swift): review for chapter_computational_complexity

* feat(swift): review for chapter_data_structure

* feat(swift): review for chapter_array_and_linkedlist

* feat(swift): review for chapter_stack_and_queue

* feat(swift): review for chapter_hashing

* feat(swift): review for chapter_tree

* feat(swift): add codes for heap article

* feat(swift): review for chapter_heap

* feat(swift): review for chapter_graph

* feat(swift): review for chapter_searching

* feat(swift): review for chapter_sorting

* feat(swift): review for chapter_divide_and_conquer

* feat(swift): review for chapter_backtracking

* feat(swift): review for chapter_dynamic_programming

* feat(swift): review for chapter_greedy

* feat(swift): review for utils

* feat(swift): update ci tool

* feat(swift): trailing closure

* feat(swift): array init

* feat(swift): map index
2024-03-20 21:15:39 +08:00

110 lines
3.7 KiB
Swift
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: knapsack.swift
* Created Time: 2023-07-15
* Author: nuomi1 (nuomi1@qq.com)
*/
/* 0-1 */
func knapsackDFS(wgt: [Int], val: [Int], i: Int, c: Int) -> Int {
// 0
if i == 0 || c == 0 {
return 0
}
//
if wgt[i - 1] > c {
return knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
}
// i
let no = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
let yes = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
//
return max(no, yes)
}
/* 0-1 */
func knapsackDFSMem(wgt: [Int], val: [Int], mem: inout [[Int]], i: Int, c: Int) -> Int {
// 0
if i == 0 || c == 0 {
return 0
}
//
if mem[i][c] != -1 {
return mem[i][c]
}
//
if wgt[i - 1] > c {
return knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
}
// i
let no = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
let yes = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
//
mem[i][c] = max(no, yes)
return mem[i][c]
}
/* 0-1 */
func knapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// dp
var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
//
for i in 1 ... n {
for c in 1 ... cap {
if wgt[i - 1] > c {
// i
dp[i][c] = dp[i - 1][c]
} else {
// i
dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[n][cap]
}
/* 0-1 */
func knapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
let n = wgt.count
// dp
var dp = Array(repeating: 0, count: cap + 1)
//
for i in 1 ... n {
//
for c in (1 ... cap).reversed() {
if wgt[i - 1] <= c {
// i
dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
}
}
}
return dp[cap]
}
@main
enum Knapsack {
/* Driver Code */
static func main() {
let wgt = [10, 20, 30, 40, 50]
let val = [50, 120, 150, 210, 240]
let cap = 50
let n = wgt.count
//
var res = knapsackDFS(wgt: wgt, val: val, i: n, c: cap)
print("不超过背包容量的最大物品价值为 \(res)")
//
var mem = Array(repeating: Array(repeating: -1, count: cap + 1), count: n + 1)
res = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: n, c: cap)
print("不超过背包容量的最大物品价值为 \(res)")
//
res = knapsackDP(wgt: wgt, val: val, cap: cap)
print("不超过背包容量的最大物品价值为 \(res)")
//
res = knapsackDPComp(wgt: wgt, val: val, cap: cap)
print("不超过背包容量的最大物品价值为 \(res)")
}
}