The Knapsack Problem
Let's apply what we're learned so far to a slightly more interesting
problem. You are an art thief who has found a way to break into the
impressionist wing at the Art Institute of Chicago. Obviously you can't
take everything. In particular, you're constrained to take only what
your knapsack can hold — let's say it can only hold W pounds. You also
know the market value for each painting. Given that you can only carry W
pounds what paintings should you steal in order to maximize your
profit?
First let's see how this problem exhibits both overlapping subproblems
and optimal substructure. Say there are n paintings with weights w1
, ..., wn
and market values v1
, ..., vn
.
Define A(i,j) as the maximum value that can be attained from
considering only the first i items weighting at most j pounds as
follows.
Obviously A(0,j) = 0 and A(i,0) = 0 for any i ≤ n and j ≤ W. If wi
> j then A(i,j) = A(i-1, j) since we cannot include the ith
item. If, however, wi
≤ j then A(i,j) then we have a choice: include the ith
item or not. If we do not include it then the value will be A(i-1, j). If we do include it, however, the value will be vi
+ A(i-1, j - wi
). Which choice should we make? Well, whichever is larger, i.e., the maximum of the two.
Expressed formally we have the following recursive definition
This problem exhibits both overlapping subproblems and optimal
substructure and is therefore a good candidate for dynamic programming.
The subproblems overlap because at any stage (i,j) we might need to
calculate A(k,l) for several k < i and l < j. We have optimal
substructure since at any point we only need information about the
choices we have already made.
http://20bits.com/article/introduction-to-dynamic-programming
分享到:
相关推荐
背包问题近似算法PTAS和FPTAS. The Knapsack Problem and Fully Polynomial Time Approximation Schemes (FPTAS). 作者: Katherine Lai, Prof. M. X. Goemans
An improved genetic algorithm for the multi constrained 0–1 knapsack problem 使用遗传算法解决多维背包问题。
KnapsackProblem,背包问题, 开发语言Java
0/1背包问题
java动态规划算法
PSO Approach For Solving Knapsack Problem
matlab开发-Knapsackproblem。一个著名的组合问题
Solving 0-1 knapsack problem using genetic algorithm
c++ knapsack problem
01背包问题(0/1 Knapsack Problem)是一个经典的动态规划问题,其描述为:给定一个固定容量的背包和一组物品,每个物品有对应的重量和价值,要求在不超过背包容量的情况下,装入背包的物品总价值最大。 定义了一个...
Knapsack_Problem In Matlab
基于core的动态规划解法,发表于著名杂志operations research的经典文章
Genetic Algorithm for multi objective knapsack problem
genetic Approach For Solving Knapsack_Problem
背包问题(Knapsack Problem)是一个经典的组合优化问题,通常分为两种类型:0/1背包问题和分数背包问题。 1. **0/1背包问题**: - 给定一组物品,每个物品都有自己的重量和价值,要求在给定的背包容量下,选择...
背包问题(Knapsack problem)是一种组合优化的NP完全问题
动态规划解决0-1背包问题-0-1 knapsack problem.zip
动态规划解决0-1背包问题-0-1 knapsack problem.rar