1 00:00:00,320 --> 00:00:04,940 Okay guys Discrete Optimization. We going to start very, very slowly. 2 00:00:04,940 --> 00:00:07,540 So what you're going to see here is amazingly simply. 3 00:00:07,540 --> 00:00:08,660 We are building the intuitions. 4 00:00:08,660 --> 00:00:14,790 And in the next couple of lectures, we are basically solving these knapsack problems. 5 00:00:14,790 --> 00:00:18,080 Going from very simple things to more interesting things, okay? 6 00:00:18,080 --> 00:00:20,450 So, we want to introduce greedy algorithm. 7 00:00:20,450 --> 00:00:22,730 And what would Indiana Jones do if he 8 00:00:22,730 --> 00:00:25,590 doesn't know anything about discrete optimization and hasn't 9 00:00:25,590 --> 00:00:29,040 taken the class in Coursera, right? So, this is what you have. 10 00:00:29,040 --> 00:00:32,990 The temple is collapsing and you have all these beautiful artifacts, right? 11 00:00:32,990 --> 00:00:37,840 So you have the Agamemnon mask. You have the Terracotta warriors. 12 00:00:37,840 --> 00:00:39,390 You have the Sumerian tablets. 13 00:00:39,390 --> 00:00:42,930 And of course, you know, Indiana Jones is pretty smart, right? 14 00:00:42,930 --> 00:00:47,430 So he can evaluate the value of every one of these item immediately right? 15 00:00:47,430 --> 00:00:51,470 So, 13 millions for the mask, 1 million for 16 00:00:51,470 --> 00:00:55,070 the, the little statues over there, right? So the warrior. 17 00:00:55,070 --> 00:00:58,940 Okay so now what Indiana Jones is going to say, he's going to say oh, but I also 18 00:00:58,940 --> 00:01:01,670 have to evaluate the size of my knapsack 19 00:01:01,670 --> 00:01:03,360 and he can figure it out very quickly right? 20 00:01:03,360 --> 00:01:05,550 So this is about ten kilos, okay? 21 00:01:05,550 --> 00:01:09,120 And then obviously what he has to do and once again he's really clever, right? 22 00:01:09,120 --> 00:01:13,350 He has to evaluate the, the weight of every one of these artifacts as well. 23 00:01:13,350 --> 00:01:16,770 Okay? And once you have all these things, okay? 24 00:01:16,770 --> 00:01:19,230 What Indiana Jones is going to do is to say okay I'm going to 25 00:01:19,230 --> 00:01:22,250 pick up the right ones, what I believe are the right ones. 26 00:01:22,250 --> 00:01:24,040 Not knowing anything about optimization. 27 00:01:24,040 --> 00:01:25,990 And of course you can't resist, right? 28 00:01:25,990 --> 00:01:29,380 The first thing you're going to do is take this mask, it's so beautiful, right? 29 00:01:29,380 --> 00:01:31,050 So that's the first thing he does okay? 30 00:01:31,050 --> 00:01:33,170 And obviously that's eight kilos. 31 00:01:33,170 --> 00:01:37,570 So there is only two kilos left inside the knapsack, okay? 32 00:01:37,570 --> 00:01:41,300 So essentially, these items cannot be selected anymore. 33 00:01:41,300 --> 00:01:41,900 The only thing 34 00:01:41,900 --> 00:01:44,548 which is left are the warriors there. 35 00:01:44,548 --> 00:01:46,620 And Indiana Jones is going to select one of them 36 00:01:46,620 --> 00:01:50,040 and then exhaust the capacity of its, of its knapsack. 37 00:01:50,040 --> 00:01:54,800 Okay, the value here is about 14, is exactly 14 millions. 38 00:01:54,800 --> 00:01:57,320 And the whole point of this class is going to say. 39 00:01:57,320 --> 00:01:58,660 Can we do better than this? 40 00:01:59,670 --> 00:02:02,100 One of the things we'll do here, is talk in 41 00:02:02,100 --> 00:02:04,740 the first, in the next lecture is talk about greedy algorithm. 42 00:02:04,740 --> 00:02:07,180 And what you just saw is essentially, a very 43 00:02:07,180 --> 00:02:08,800 simple instance of a greedy algorithm. 44 00:02:08,800 --> 00:02:11,710 We take the most valuable item first and then 45 00:02:11,710 --> 00:02:14,820 the next valuable item that can fit into a knapsack. 46 00:02:14,820 --> 00:02:17,010 But there are many, many possible greedy algorithms. 47 00:02:17,010 --> 00:02:20,240 In the next lecture, we'll review some of them. 48 00:02:20,240 --> 00:02:21,990 And then afterwards, what we'll do 49 00:02:21,990 --> 00:02:24,320 is basically look at more sophisticated technique. 50 00:02:24,320 --> 00:02:27,010 I told you, very simple lecture, this is the first one. 51 00:02:27,010 --> 00:02:27,700 See you next time.