第15章——动态规划（上2）
文章目录
Knapsack Problem
问题描述——The famous knapsack problem:
A thief breaks into a museum. Fabulous paintings, sculptures, and jewels are everywhere. The thief has a good eye for the value of these objects, and knows that each will fetch hundreds or thousands of dollars on the clandestine art collector’s market. But, the thief has only brought a single knapsack to the scene of the robbery, and can take away only what he can carry. What items should the thief take to maximize the haul?
一个小偷闯进了博物馆。令人难以置信的绘画、雕塑和到处都是珠宝。这个小偷有很好的鉴赏力这些对象，并知道每一个将在秘密的艺术品收藏市场上获得数百或数千的美元。但是，小偷有只带了一个背包到抢劫现场，而且可以只带走他能带走的东西。小偷应该最大限度地拖带走什么东西 ?
问题参数：
Given a knapsack with maximum capacity W,
and a set S consisting of n items
Each item i has some weight wi and benefit value bi (all wi , bi and W are integer values)
Problem: How to pack the knapsack to achieve maximum total value of packed items?
- More formally, the 0-1 knapsack problem:
The thief must choose among n items, where the ith item worth vi dollars and weighs wi pounds Carrying at most W pounds, maximize value
Note: assume vi, wi, and W are all integers
“0-1” each item must be taken or left in entirety
- Generalization, the unbounded knapsack problem: No bound on the number of each item Think about the thief ran into a bank…
问题求解：
1. 0-1 Knapsack – Formulation（公式化）
- 0-1 Knapsack problem: brute-force approach（暴力求解)
Let’s first solve this problem with a straightforward algorithm.Since there are n items, there are possible combinations of items. We go through all combinations and find the one with the most total value and with total weight less or equal to W. Running time will be O().
- 动态规划 - Can we do better?
Yes, with an algorithm based on dynamic programming We need to carefully identify the subproblems
Let’s try this:
If items are labeled 1…n, then a subproblem would be to find an optimal solution for
OPT(k) = {items labeled 1, 2, … k}
This is a valid subproblem definition. The question is: can we describe the final solution OPT(n) in terms of subproblems OPT(1),OPT(2),…,OPT(n-1)? Unfortunately, we can’t do that. Explanation follows….
defining a subproblem
As we have seen, the solution for OPT(4) is not part of the solution for OPT(5). So our definition of a subproblm is flawed and we need another one! Let’s add another parameter: w, which will represent the exact weight for each subset of itemsThe subproblem then will be to compute OPT[i,w]