Ming
0%

knapsack problem

Posted on Edited on In

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

0-1 knapsack

A thief robs a store and finds n items, with item i being worth $Vi and having weight Wi pounds. The thief can carry at most W∈ N in his knapsack but he wants to take as valuable a load as possible. Which item should he take?

Fractional knapsack

The setup is same as 0-1 knapsack, but the thief can take fractions of items

Optimal Substructure

Both knapsack problems exhibit the optimal substructure property:

  1. For 0-1 knapsack problem, if we remove item j from this load, the remaining load must be at most valuable items weighing at most W-wj from n-1 items.
  2. For fractional one, if we remove a weight w of one item j from the optimal load, then the remaining load must be the most valuable load weighing at most W-w that the thief can take from the n-1 original items plus wj-w pounds of item j

Example

There are 5 items that have a value and weight list below, the knapsack can contain at most 100 Lbs. Solve the problem both as fractional knapsack and 0/1 knapsack.

0-1 knapsack

dp[i][j]表示在前i个物品，背包容量为j情况下的最优解。

转换关系为：

1
2
3
4
5
if j < weights[i-1] {
	dp[i][j] = dp[i-1][j]
} else {
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
}

完整过程：

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
package main

import (
	"fmt"
)

func main() {
	fmt.Println(knapsack([]int{20, 30, 65, 40, 60}, []int{10, 20, 30, 40, 50}, 100)) // 0-1 knapsack
}

// 0-1 knapsack
func knapsack(values, weights []int, cap int) int {
	n := len(values)
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, cap+1)
	}

	for i := 1; i <= n; i++ {
		for j := 1; j <= cap; j++ {
			if j < weights[i-1] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
			}
		}
	}
	return dp[n][cap]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Fractional knapsack

先将所有物品按单价排序（降序），优先选取单价最高的，如果背包容量足够，就全拿走，否则尽量多拿，结束循环。

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
46
47
48
49
50
51
52
package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(_knapsack([]int{20, 30, 65, 40, 60}, []int{10, 20, 30, 40, 50}, 100)) // fractional knapsack
}

// fractional knapsack
func _knapsack(values, weights []int, cap float64) float64 {
	n := len(values)
	var items Items
	for i := 0; i < n; i++ {
		items = append(items, Item{float64(values[i]), float64(weights[i])})
	}
	sort.Sort(items)

	var ans float64
	for _, item := range items {
		if cap >= item.weight {
			ans += item.value
			cap -= item.weight
		} else {
			ans += (item.value / item.weight) * cap
			break
		}
	}
	return ans
}

type Item struct {
	value  float64
	weight float64
}

type Items []Item

func (items Items) Len() int {
	return len(items)
}

func (items Items) Less(i, j int) bool {
	return !(items[i].value/items[i].weight < items[j].value/items[j].weight)
}

func (items Items) Swap(i, j int) {
	items[i], items[j] = items[j], items[i]
}

LeetCode

LeetCode-416 | Ming (m1ng.xyz)

LeetCode-322 & LeetCode-518 | Ming (m1ng.xyz)

1049. 最后一块石头的重量 II