这段代码只是使用暴力法解决了01背包问题,但是没有经过优化,效率不高。
使用暴力法的原因只是因为作业需求,请勿评价。
主要的难点在于使用C语言列出一个数组的所有子集。使用了递归的方法,将每次的计算都归并为二个元素,这样就能够简化问题。
//
// main.c
// BackPack
//
// Created by shadowdai on 11-10-25.
// Copyright 2011年 __MyCompanyName__. All rights reserved.
//
#include <stdio.h>
//k是开始字符的位置,n是数组的长度,l是子集的位数
void subArray(int W[], int V[], int k,int l, int n);
//初始化整个子集数组
void initArray(int n);
//用于输出子集的数组
int priArray[4];
void printArray(int W[], int n);
//计算子集的个数
int counter;
int subArrayWeight[16];
int subArrayValue[16];
//计算子集的重量和价值
void sumOfWeightAndValue(int W[], int V[], int m, int n);
//寻找重量不超过背包重量,并且价值最大的子集
int searchMax();
//重量和价值数组
int main()
{
int i;
int max;
int array[4] = {7, 3 , 4, 5};
int value[4] = {42, 12, 40, 25};
//0是所有数组的子集
printf("The No.1 is: 0\n");
subArrayWeight[0] = 0;
subArrayValue[0] = 0;
counter = 1;
for (i = 0; i < 4; i++)
{
initArray(4);
//递归算法需要保证从第一个元素开始的所有的元素都被遍历到
priArray[0] = i;
counter ++;
sumOfWeightAndValue(array, value, counter, 1);
printArray(array, 1);
subArray(array, value, i+1, 2, 4);
}
printf("\nThere are %d SubArray.\n", counter);
for (i = 0; i < 16; i++)
{
printf("The Weight of %d is %d and the value is %d\n", i+1 , subArrayWeight[i], subArrayValue[i]);
}
max = searchMax();
printf("\nThe most valuable package is No.%d, the max value is %d.\n", max+1, subArrayValue[max]);
return 0;
}
/*
* 该递归算法每次只向后寻找一位数字。
* 例如k=1时,只会寻找2,3,4;k=2时,只会寻找3,4
*/
void subArray(int W[], int V[], int k, int l, int n)
{
int i;
if (k == n-1)
{
//n是整个数组的长度,k是整个子集的上一位字符,当k == n-1时,意味着已经是最后一个了。
priArray[l-1] = k;
counter += 1;
sumOfWeightAndValue(W, V, counter, l);
printArray(W, l);
}
else
{
for ( i= k; i <= n-1; ++i)
{
priArray[l-1] = i;
counter += 1;
sumOfWeightAndValue(W, V, counter, l);
printArray(W, l);
subArray(W, V, i+1, l+1,n);
}
}
}
/*
* 打印子集数组的函数
*/
void printArray(int W[], int n)
{
int i;
printf("The No.%d is: " , counter);
for (i = 0; i < n; i++)
{
printf("%d ", W[priArray[i]]);
}
printf("\n");
}
/*
* 初始化子集数组
*/
void initArray(int n)
{
for (int i = 0; i<= n-1 ; i++) {
priArray[i] = 0;
}
}
/*
* 计算子集的重量和价值综合
* m是该子集的序号,与counter相同。n是数组长度
*/
void sumOfWeightAndValue(int W[], int V[], int m, int n)
{
int i;
int sumWeight = 0, sumValue = 0;//重量和价值总和变量
for ( i = 0; i < n; i++) {
sumWeight += W[priArray[i]];
sumValue += V[priArray[i]];
}
subArrayWeight[m-1] = sumWeight;
subArrayValue[m-1] = sumValue;
}
/*
* 排序并查找所有子集中最大子集
*/
int searchMax()
{
int i,max,MAX;
max = 0;
MAX = subArrayValue[max];
for (i = 0; i < 16; i++) {
if (subArrayWeight[i] <= 10)
{
if (subArrayValue[i] >= MAX)
{
max = i;
MAX = subArrayValue[max];
}
}
}
return max;
}
分享到:
相关推荐
关于用回溯法求解01背包问题的源程序,里面附有说明,希望对你们有帮助
算法设计实验报告,包括:贪心法求解背包问题的基本思想、动态规划法求解0/1背包问题的基本思想及各自的时间复杂度分析,两种问题的区别,C++实现代码,运行截图,实验心得。
完全版分支界限法求解背包问题,易于理解 分支界限法0-1背包问题
01背包问题是一个很经典的问题,在这里我用回溯法解决。希望大家一起来探讨呀!
【背包问题】基于PSO算法求解01背包问题
主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
贪心方法:总是对当前的问题作最好的选择,也就是局部寻优。最后得到整体最优。应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个...
带有贪心策略的离散粒子群算法用于求解01背包问题
【背包问题】基于遗传算法求解多背包问题matlab源码
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
回溯法求解背包问题
为C语言课程设计写的基于贪心法的背包问题,包含全部4种贪心策略
本代码大量注释,便于理解。回溯法解决01背包问题,相对于动态规划来说,我们首先得了解问题的解空间,了解解空间的组织结构,最后搜索解空间,其中加入约束条件和限界条件是关键,否则就是穷举了。
01背包问题的回溯法求解:使用纯C编写,采用回溯递归求解。
回溯法01背包问题.cpp
C++分支限界法(BFS求解01背包问题)
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。
matlab遗传算法求解0-1背包问题.zip
利用回溯法求解,建立空间n叉树,先用快速排序以方便查找。