<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step1:  Dynamic programming solves a problem by breaking it up into smaller sub-problems, looks up the answer or solves and saves results and then combines the answers together to solve the original problem. 
Key question
Step2:  Now what if we use a list
Step3:  Now there isn't any point in saving all the fib numbers, so modifying the code to save only the last two fib numbers
Step4:  The recursion fails as exceeds max memory depth on pretty small fib numbers
Step5:  Now this holds all the fib numbers up to n in memory in a list. Which for large n seems un necessary to waste all that memory.
Step6:  Knapsack problem
Step7:  The most recent year where we have info on all three is 2011, so lets look at 2011 data
Step8:  So now we have a dataframe containing country names, their population, adjusted per capita income and life expectance.
To simplify things, I'm going to drop the missing values
Step10:  Lets say we want 500 million people with the highest income. So the population becomes the "weights", and the income the "values" of this knapsack problem.
So lets divide this problem into sizes of 10M, so we go 10, 20, 30... all the way to 500M
first, starting with 10 to 50M to keep it simple, heres our table
<ASSISTANT_TASK:>
Python Code:
def fib_recursion(n, table=[]):
    returns fib of n
    
    if n <= 1:
        return n
    
    if len(table) < 1:
        table = np.zeros(n+1)
    if table[n-1] == 0:
        table[n-1] = fib_recursion(n-1, table)
    if table[n-2] == 0:
        table[n-2] = fib_recursion(n-2, table)
    
    table[n] = table[n-1] + table[n-2]
    
    return table[n]
[fib_recursion(n) for n in range(10)]
Explanation: Dynamic programming solves a problem by breaking it up into smaller sub-problems, looks up the answer or solves and saves results and then combines the answers together to solve the original problem. 
Key question:
- What are the sub problems?
A simple example:
Fib numbers using dynamic programming
End of explanation
def fib_list(n):
    table=[0,1]
    for i in range(2, n+1):
        table.append(table[i-1]+table[i-2])
    return table[n]
        
[fib_list(n) for n in range(10)]      
Explanation: Now what if we use a list:'
End of explanation
def fib_list_two(n):
    table=[0,1]
    
    for i in range(2, n+1):
        table.append(sum(table[-2:]))
        del table[0] 
    return table[1]
        
[fib_list_two(n) for n in range(10)]
%time fib_recursion(100)
Explanation: Now there isn't any point in saving all the fib numbers, so modifying the code to save only the last two fib numbers:
End of explanation
%time fib_list(1000)
Explanation: The recursion fails as exceeds max memory depth on pretty small fib numbers
End of explanation
%time fib_list_two(1000)
Explanation: Now this holds all the fib numbers up to n in memory in a list. Which for large n seems un necessary to waste all that memory.
End of explanation
income_url="http://docs.google.com/spreadsheet/pub?key=0AkBd6lyS3EmpdHo5S0J6ekhVOF9QaVhod05QSGV4T3c&output=xlsx"
life_url="http://docs.google.com/spreadsheet/pub?key=phAwcNAVuyj2tPLxKvvnNPA&output=xlsx"
pop_url="http://docs.google.com/spreadsheet/pub?key=phAwcNAVuyj0XOoBL_n5tAQ&output=xlsx"
income = pd.read_excel(income_url)
life = pd.read_excel(life_url)
pop = pd.read_excel(pop_url)
income.head()
life.head()
pop.head()
Explanation: Knapsack problem
End of explanation
df = pop[["Total population", 2011]].copy()
df.rename(columns={2011: "Population"}, inplace=True)
df.head()
df = df.join(life[2011])
df.rename(columns={2011: "Life"}, inplace=True)
df.head()
df = df.join(income["2011"])
df.rename(columns={"2011": "Income"}, inplace=True)
df.head()
Explanation: The most recent year where we have info on all three is 2011, so lets look at 2011 data:
End of explanation
df.dropna(inplace=True)
df.head()
Explanation: So now we have a dataframe containing country names, their population, adjusted per capita income and life expectance.
To simplify things, I'm going to drop the missing values:
End of explanation
solved = pd.DataFrame(columns=np.arange(10,51,10), index=df["Total population"])
solved.fillna(value=0, inplace=True)
solved.head()
ans = {}
ans[10] = 100, 200, ["countryA", "B"]
ans[10]
def pop_income(pop_size):
    takes in a pop_size, and returns a tuple containing
    max income and pop and a list of countries chosen
    if pop_size in solved.keys():
        return solved[max]
    pop = 0
    income = 0
    
    for i, row in df[df["Population"]<= pop_size].iterrows():
        print(row)
pop_income(10*np.power(10,4))
np.power(10,9)  
Explanation: Lets say we want 500 million people with the highest income. So the population becomes the "weights", and the income the "values" of this knapsack problem.
So lets divide this problem into sizes of 10M, so we go 10, 20, 30... all the way to 500M
first, starting with 10 to 50M to keep it simple, heres our table:
End of explanation
<END_TASK>