[算法]背包问题的经典算法和贪心算法解答，C语言实现

圣诞前夜讲点比较具有圣诞感觉的算法，背包问题算法，这里我写了经典算法和贪心算法两种解决方法，因为时间不多，所以给出的数组是已经排序的，因为贪心算法可能要用得到，经典算法因为是一个一个比较，因此排序也就没有那么重要了，可能两种算法的最终运行效果一样的，朋友们调试的时候记得修改我给出的测试数组，今天实在太忙了，贪心使用的排序算法没有写，留着以后给大家讲排序算法的时候使用吧，圣诞快乐，诸位朋友们。 背包问题：就是现在有一个容量为PSIZE的背包，同时又有N件item，现在要求将这些item放入这个背包里面去，要求尽量放一定要求的item（比如按照大小的顺序），又要求放最多的item或者放的item权值之和要最大 问题讲完，算法如下，C语言实现，另外回溯、动态规划的算法，有时间也会写上，今天 实在太忙了，诸位朋友继续期待吧： /*背包问题之经典解法和贪心算法*code cg*2008 12 24*调试环境TC ，devC++*/#include "stdio.h"#include "stdlib.h"#include "conio.h"#define N 5 /*定义需要放的物件数量*/#define PSIZE 150/*定义背包大小*/long item[N]={15,40,50,60,90};/*初始化物件数组，贪心算法要求大小已排序*/int freespace[N]={0};int classic() {/*经典算法*/long size = PSIZE;long used = 0;int i; for(i = N - 1 ; i >= 0 ; i--){ if((size - used) >= item[i]){/*大小可以放入吗？*/ used += item[i]; /*放入背包 已使用数加新物件的大小*/ freespace[i] = 1; } else { /*大小太大*/ freespace[i] = 0; } }/*for*/ return 1;}int greedy(){/*贪婪算法*/int i;long size = PSIZE;long used = 0;for(i = N - 1 ; i >= 0 ; i--){/*先放大的物体，再考虑小的物体*/ if( (used + item[i]) < sizebr> freespace[i] = 1;/*1表示放入*/ used += item[i];/*背包剩余容量减少*/ } else{ freespace[i]=0; }}/*for*/if(size == used)/*返回*/ return 1;else return 0;}void main(){int i;/*计数器*/for(i = 0 ; i < N ibr> if(i % 5 == 0 ) printf("n"); printf("%10ld" , item[i]);/*首先输入原始数据*/ }/*for*/printf("nClassicn");if(classic()==1){/*经典算法*/ printf("Result:n"); for(i=0;i if(freespace[i] == 1){ if(i % 5 == 0) printf("n"); printf("%10ld" , item[i]); }/*if*/ }/*for*/ }/*if*/ else { printf("nNo Resultn"); } for(i = 0 ; i < N ibr> freespace[i]=0 ; /*清空freespace数组*/ printf("nGreedyn"); if(classic()==1){/*经典算法*/ printf("Result:n"); for(i=0;i if(freespace[i] == 1){ if(i % 5 == 0) printf("n"); printf("%10ld" , item[i]); }/*if*/ }/*for*/ }/*if*/ else{ printf("nNo Resultn"); } system("PAUSE"); } -------------------------------------------------------------------------------------- - 版权声明： - 如在本页面内无特别说明，本文内容均为[李大仁博客]原创，本文版权归[李大仁博客]所有。 - 欢迎转载，转载请务必在文章页面明显位置提供原文链接并注明出处。欢迎您在转载本文时保留本段声明。 - 文章标题： 背包问题贪心、回溯、动态规划、经典解法的两个经典解法 - 独立博客： 李大仁博客 - 永久链接：http://www.lidaren.com/archives/263 -------------------------------------------------------------------------------------- 以上内容由博客自动发布工具自动发布，最终显示内容和效果会与原文内容有所偏差，敬请谅解。