计算机科学与Python编程导论 13次作业（背包与图的最优化问

1.最优化问题提供了一种结构化的方法，可以解决很多计算问题。最优化问题通常包括两部分：1）目标函数：需要最大化或最小化的值。2）约束条件集合（可以为空）：必须满足的条件集合。

2.动态规划
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中， 可能会有很多可行解。没一个解都对应于一个值，我们希望找到具有最优值的解。胎动规划算法与分治法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适用于动态规划算法求解的问题，经分解得到的子问题往往不是互相独立的。

3.背包问题
举例：有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，每件物品数量只有一个，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

include <iostream>
using namespace std;

int knapsack(int *W, int *V, int *res, int n, int C)
{
int value = 0;
int *f = new int[n];
for(int i = 0; i < n; I++)
{
f[i] = new int[C+1];
}

for(int i = 0; i < n; I++)
    for(int j = 0; j <= C;j++)
        f[i][j] = 0;

for(int i = 0; i < n; I++)
{
    f[i][0] = 0;
}
for(int i = 1; i <= C; I++)
{
    f[0][i] = (i < W[0])?0:V[0];
}
for(int i = 1; i < n; I++)
{
    for(int y = 1; y <= C; y++)
    {
        if(y >= W[I])
        {
            f[i][y] = (f[i-1][y] > (f[i-1][y-W[i]] + V[i]))?f[i-1][y]:(f[i-1][y-W[i]] + V[I]);
        } else {
            f[i][y] = f[i-1][y];
        }
    }
}

for(int i = 0; i < n; I++)
{
    for(int j = 0; j < C+1;j++)
       cout << f[i][j] << " ";
    cout << endl;
}

value = f[n-1][C];
int j = n-1;
int y = C;
while(j)
{
    if(f[j][y] == (f[j-1][y-W[j]] + V[j]))
    {
        res[j] = 1;
        y = y - W[j];
    }
    j--;
}
if(f[0][y])
{
    res[0] = 1;
}

for(int i = 0; i < n;i++)
{
    delete f[I];
    f[i] = 0;
}
delete [] f;
f = 0;
return value;

}

void test1()
{
int n, C;
while(cin >> n >> C)
{
int *W = new int[n];
int *V = new int[n];
int *res = new int[n];
for(int i = 0; i < n; I++)
{
res[i] = 0;
}
int w = 0, v = 0, i = 0;
while(i < n)
{
cin >> w >> v;
W[i] = w;
V[i] = v;
I++;
}
int value = knapsack(W, V, res, n, C);
cout << value << endl;
for(int i = 0; i < n; I++)
cout << res[i] << " ";
cout << endl;
delete W;
delete V;
delete res;
}
}

int main()
{
test1();
return 0;
}

4.图的相关问题
从数学上讲，图由顶点的集V和边的集E构成，其中E中的每一条边都连接V中的两个顶点。顶点和边可以带标签，也可以不带标签。当边带有数字标签的时候，可以将这些数字看做为权重（weight）,并且说这个图是一个加权图。

图的示例.png

（1）可以用字典和列表来表示
graph = {'V0':['V1','V5'],
'V1':['V2'],
'V2':['V3'],
'V3':['V4','V5'],
'V4':['V0'],
'V5':['V2','V4']}

（2）找到一条路径
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None

（3）找到最短路径
def find_shortest_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest

5.错题
1.BFS的查询的时间复杂度为O(n).

2. 错题2.png 3. 错题3.png