|
课堂上老师是从找零问题（即给一些不同面值种类的钱币，用户输入一定金额，要求输出用最少的个数的钱币组合）开始引入的贪心算法，分治思想以及动态规划方法。日常生活中我们也许没有注意到，自己在处理找零问题时总是采用的是贪心算法，每次都从最大面值的钱币开始，直至剩余值小于最大面值，才开始选取更小一点的面值，这样的方法简单，复杂度低，但是不一定能得到全局最优的结果。而分治思想就是把一个复杂的大问题分解成几个完全独立的子问题进行解决，动态规划则不然，是把问题递归为规模小一点的同类子问题，当规模最小时直接返回，需要注意的是，这里我们要存储子问题的结果，用于大问题，即消耗了更多的空间复杂度，换取了时间复杂度上的优化，而此问题下可以进一步探讨的是空间的利用。
如以下问题：
We are given 7 items and a knapsack. Each itemi has weight of wi > 0 kilograms and value of vi >0 dollars (given in table 1). The capacity of the knapsack is 14 kilograms.Then how to fill the knapsack to maximize the total value?
|
Items
|
Weight
|
Value
|
|
1
|
3
|
2
|
|
2
|
4
|
3
|
|
3
|
2
|
3
|
|
4
|
2
|
1
|
|
5
|
7
|
6
|
|
6
|
5
|
3
|
|
7
|
6
|
5
|
Table1
问题分析：对每件物品，都有选择与不选两种策略，如果用穷举的思想就有2^N种情况，这是非常糟糕的时间复杂度。这里，如果采用动态规划的思想，假设一开始袋子是空，针对前i件物品的最优解，如果含有第i件物品，则最优值为总的重量限制减去Wi；如果不含有第I件物品，则为前i-1件物品在题设条件下的总重限制，两者之间的最大值即为前i件物品的最大value.这样每次添加一件直至物品集合从空集变为全集，此时我们就考虑了所有的前n件物品。 <pre name="code" class="cpp">递推关系如此式所示：Opt[i,w]=max{Opt[i-1,w],Vi+Opt[i-1,w-wi]},注意到重量约束条件引入的变化问题，两重循环变量
<pre name="code" class="cpp">#include<vector>
#include<iostream>
#include<conio.h>
using namespace std;
//定义物品类的数据结构
typedef struct{
int weight;
int value;
}item;
//全局变量
item Item[7];
int total_weight;
//算法实现函数
int Max(int a,int b)
{
return (a>b)?a:b;
}
void initializ()
{
//用一维数组来存储测试数据
int item_weight[7]={3,4,2,2,7,5,6};
int item_value[7]={2,3,3,1,6,3,5};
int i_item;
for(i_item=0;i_item<7;i_item++)
{
Item[i_item].weight=item_weight[i_item];
Item[i_item].value=item_value[i_item];
}
total_weight=14;
}
//递归实现
int Opt(int i,int w) //i 表示前i件物品，w表示总重量限制
{
if(i==0|| w==0)
return 0;
else
if(Item[i-1].weight>w)
return Opt(i-1,w);
else
return Max(Opt(i-1,w),Item[i-1].value +Opt(i-1,w-Item[i-1].weight));
}
//找出对应最大值的背包方案
/*
void Trace_back(int i,int w)
{
int j;//循环变量
for(j=i;j>0;j--)
{
if(Opt(i,w))
}
}
*/
//测试函数
int t_main()
{
initializ();
//*******自底向上实现******//
//循环变量定义
int i,w;
int value[8][15];
for(i=0;i<=7;i++)
{
for(w=0;w<=total_weight;w++)
{
if(i==0 || w==0)
value[i][w]= 0;
else
if(Item[i-1].weight>w)
value[i][w]=value[i-1][w];
else
value[i][w]=Max(value[i-1][w],Item[i-1].value+value[i-1][w-Item[i-1].weight]);
}
}
cout<<value[7][14];
return 0;
//cout<< Opt(7,14);
//return Opt(7,14);
}
int main()
{
t_main();
getch();
return 0;
}
| 
转播
