00:00:00
OPERATOR: -- The following
content is provided under a
00:00:02
Creative Commons license.
00:00:03
Your support will help MIT
OpenCourseWare continue to
00:00:06
offer high quality educational
resources for free.
00:00:10
To make a donation, or view
additional materials from
00:00:13
hundreds of MIT courses,
visit MIT OpenCourseWare
00:00:22
PROFESSOR: At the end of the
lecture on Tuesday, a number of
00:00:27
people asked me questions,
asked Professor Grimson
00:00:30
questions, which made it clear
that I had been less than clear
00:00:35
on at least a few things, so I
want to come back and revisit a
00:00:40
couple of the things we talked
about at the end
00:00:45
You'll remember that I had
drawn this decision tree, in
00:00:58
part because it's an important
concept I want you to
00:01:00
understand, the concept of
decision trees, and also to
00:01:05
illustrate, I hope, visually,
some things related to
00:01:09
dynamic programming.
00:01:11
So we had in that decision
tree, is we had the weight
00:01:17
vector, and I just given a very
simple one [5,3,2], and we had
00:01:24
a very simple value
vector, [9,7,8].
00:01:32
And then the way we drew the
tree, was we started at the
00:01:44
top, and said all right, we're
going to first look at item
00:01:53
number 2, which was the third
item in our list of items, of
00:01:57
course, and say that we had
five pounds left of weight that
00:02:04
our knapsack that could hold,
and currently had a value of 0.
00:02:11
And then we made a decision, to
not put that last item in the
00:02:18
backpack, and said if we made
that decision, the next item we
00:02:24
had to consider was item 1, we
still had five pounds
00:02:29
available, and we still had
a weight 0 available.
00:02:35
Now I, said the next item to
consider is item 1, but really
00:02:40
what I meant is, 1 and all of
the items proceeding
00:02:47
This is my shorthand for saying
the list up to and including
00:02:52
items sub 1, kind of a normal
way to think about it.
00:02:58
And then we finish building the
tree, left first step first,
00:03:02
looking at all the no branches,
0,5,0 and then we were
00:03:09
done, that was one branch.
00:03:15
We then backed up, and said
let's look at a yes, we'll
00:03:21
include item number 1.
00:03:25
Well, what happens here, if
we've included that, it uses
00:03:33
up all the available weight,
and gave us the value of 9.
00:03:37
STUDENT: [UNINTELLIGIBLE]
00:03:41
PROFESSOR: Pardon?
00:03:44
STUDENT: -- want to be
off the bottom branch.
00:03:49
PROFESSOR: Yup, Off by 1.
00:03:52
Yeah, I wanted to come off
this branch, because I've
00:03:54
backtrack just 1, thank you.
00:04:03
And then I backtrack up
to this branch, and
00:04:09
from here we got 0,2,7.
показать еще
русский▼
English
español
italiano
日本語
中文
português
français
Deutsch
