代写data程序、代做C++语言程序、c++编程代写

日期：2021-04-07 11:01

Midterm Project: Logistic Problem in Alibaba

In the Alibaba company, we have one big warehouse, and customers need the products on

time. Based on the coming online shopping, I need to send the products to them from the

warehouse (seen in Figure 1). However, I have limited capacity in the warehouse and which

products I need to store there. The question is here which products need to be in the

warehouse before sending to customers. I will store and deliver my products dynamically.

This problem is an actual use case of the Knapsack Problem, and we store and deliver the

products dynamically. We need to understand the knapsack problem and dynamic

programming (shared as an extra file).

Knapsack Problem algorithm is a very helpful problem in combinatorics. In the warehouse

there are n packages the package i has weight (Wi) and value (Vi). The company cannot store

the products if the total products weights are greater than capacity. The problem to be solved

here is: which packages will the company deliver to get the highest value?

Project Definition:

The Problem here we have 300 instances (trials). For each instance, we have C, Vi, and Wi for

the problem.

Capacity will be generated by using normal distribution as mean: 130 and standard deviation:

30. It means that we will generate the capacity between 100 and 160 for each instance. We

shared all values and weights in the datasets for the project. For each instance, which item we

need to select for getting more value and using less capacity.

Which items should Alibaba put in Warehouse to maximize value?

Simple Examples for Knapsack Problem

Let me explain Knapsack problem with examples.

Note: Instance here is the trial or combinations of items. For each knapsack instance,

For this example, we generated the capacity as 7 then we would like to optimize the total

values. We need to select the items that have minimum weights and maximum values. I will

add each item dynamically and check my instance capacity. When we select;

Item 1 (V:10, W:2) + Item 2 (V:10, W:3) + Item 4 (V:2, W:1) = Total V:22, W:6 so, W<C as 6<=7

with 22 values.

Item 2 (V:10, W:3) + Item 3 (V:12, W:4) = Total V:22, W:7 so, W<C as 7<=7 with 22 values.

Then, we will store [Item 1 and Item 2] or [Item 2 and Item 3] for this instance.

What we will do in the Project:

In the Project:

? 300 Warehouse (Knapsack) Instances

? For each instance, we need to define C in Normal Distribution[Mean:130, Standard

Deviation:30]

? Only find out C once you choose which items to put in the warehouse (knapsack)

? If you go over C, then you get nothing for that instance

We generated 300 C for 300 instances. For example, let’s say that we generated 125 lbs, for

Instance 1. It means that we store the items based on this capacity. As seen below, total space

consumption cannot pass 125, for Instance 1.

Here is how we’ll give you the knapsack instances:

How to Submit the Project

You need to define 0 or 1 in this CSV file. 1 means that Alibaba do store this item on the

warehouse asseen below. For example, for instance 1, we selected item 1 and item 2 and total

space consumption is 30+63=93. This 93 is less than 125. As a reward, we earned 18.12 + 35.2

dollars. So, we need to assign these 0s and 1s for earning more by using less capacity.

In the evaluation.ipynb file, you will show that how much you are earned. Moreover, you will

show all assignments in this CSV files for submission.

After defined all packages (items) to warehouse, we need to find the optimum way by

using monte carlo simulation. It means that we will use the average of all values for

showing.

Conservative Approach

Assume the size of the knapsack is 100 for all instances

– This way you will never go over

? Find best way to pack knapsack.

– Develop a few heuristics.

– For each instance of the knapsack problem, pass the instance to each heuristic and then pick

the best.

If I assume all knapsacks have size 100, I might be leaving points on the table.

– Use Monte Carlo to find a good mix of knapsack sizes.

– Start by assuming all knapsacks are the same size.

Output: In this project, we need to show the best way to pack the warehouse (knapsack).

For example, we have 300 instances (trials). Please show which instance is the best and how

much we will earn.

Note: You need to use Monte Carlo Simulation for this part.

Grading

? 27 points total

7 points towards how good your solution is

? Top Three Place (among all groups across sessions) – 7 points

? Rest of top 33% - 5 points

? Middle 33% - 3 points

? Bottom 33% - 2 point

20 points towards the fact your code actually runs.

? Your code needs to pass the auto-grader and provides a nonnegative value.