一步步学算法(算法题解)---4
本人大二，最近开始自学算法，在此记录自己学习过程中接触的习题。与君共勉。
水平有限，目前涉及的题目都比较水。
题目分布为5+1. 5为自己学习的5道水题。 1为从网上找到的比较有水平的相关题目。
一步步学算法(算法题解)---4
穷举法。
穷举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。
用穷举算法解决问题，通常可以从两个方面进行分析：
一、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。
二、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。把这些条件描述出来。
问题描述:
#include <stdio.h>#include <math.h>#define MAX 100 // 限定最多物品数/*将n化为二进制形式，结果存放到数组b中*/void conversion(int n,int b[MAX]){ int i; for(i=0;i<MAX;i++) { b[i] = n%2; n = n/2; if(n==0)break; } }int main(){ int i,j,n,b[MAX],temp[MAX]; float tw,maxv,w[MAX],v[MAX],temp_w,temp_v; printf("please input n:\n"); scanf("%d",&n); // 输入物品个数 printf("please input tw:"); scanf("%f",&tw); // 输入背包的限制重量 /*输入各个物品的重量*/ for(i=0;i<n;i++) { printf("please input the weight of w[%d]:\n",i); scanf("%f",&w[i]); } /*输入各个物品的价值*/ for(i=0;i<n;i++) { printf("please input the value of v[%d]:\n",i); scanf("%f",&v[i]); } maxv = 0; /*穷举2n个可能的选择，找出物品的最佳选择*/ for (i=0;i<pow(2,n);i++) { for (j=0;j<n;j++) { b[j] = 0; } conversion(i,b); temp_v = 0; temp_w = 0; for (j=0;j<n;j++) { if (b[j]==1) { temp_w = temp_w+w[j]; temp_v = temp_v + v[j]; } } /*试探当前选择是否是最优选择，如果是就保存下来*/ if ((temp_w < tw)&&(temp_v>maxv)) { for (j=0;j<n;j++) { temp[j] = 0; } maxv = temp_v; for (j=0;j<n;j++) { temp[j] = b[j]; } } } printf("the max values is %f:\n",maxv); // 输出放入背包的物品的最大价值 printf("the selection is:\n"); /*输出物品的选择方式*/ for (j=0;j<n;j++) { printf("%d ",temp[j]); } return 0;}/********************************** 打印结果： please input n: 3 please input tw:100 please input the weight of w[0]: 30 please input the weight of w[1]: 80 please input the weight of w[2]: 60 please input the value of v[0]: 20 please input the value of v[1]: 70 please input the value of v[2]: 60 the max values is 80.000000: the selection is: 1 0 1 **********************************/