（华电科院）算法设计与分析实验报告—01背包问题(2)

} }

cout<<\最优解为:\ for(i=1;i<=n;i++) {

cout<<\第\件物品要放:\ cout<

void main() {

cout<<\运用贪心法解背包问题---------|\ int j,n; float M;

goodinfo *goods;//定义一个指针 while(j) {

cout<<\请输入物品的总数量：\ cin>>n;

goods=new struct goodinfo [n+1];// cout<<\请输入背包的最大容量：\ cin>>M; cout<

for(i=1;i<=n;i++) { goods[i].flag=i;

cout<<\请输入第\件物品的重量:\ cin>>goods[i].w;

cout<<\请输入第\件物品的效益:\ cin>>goods[i].p;

goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比 cout<

Insertionsort(goods,n); bag(goods,M,n);

cout<<\ cout<<\ cin>>j; } }

七、运行结果：

上述结果显示:

贪心算法不是总是最优的.

八、动态规划与贪心算法比较

动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。