<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
// BackPack.cpp : Defines the entry point for the console application.
//背包问题处理头文件
//背包问题的算法
/*
作者:成晓旭
时间:2001年10月12日(18:02:38-18:12:00)
内容:完成背包问题的程序
时间:2001年10月9日(14:00:00-15:00:00)
内容:完成“皇后”问题的程序序言部分
===================================================
问题描述:
在一个n*n的棋盘上放置n个不能互相捕捉的国际象棋“皇后”,
并输出所有合理的布局情况.(在国际象棋中,皇后可以沿着纵、横
及两条斜线共4个方向捕捉对手,可见,合适的解是在每行、每列及
在一条斜线上只能有一个皇后)
编程思想:
算法描述:
try(i,tw,tv)
i:物品编号
tw:当前选择已达到的物品总重量和
tv:本方案可能达到的物品总价值
{
//考虑物品i包含在当前方案中的可能性
if(包含物品i是可接受的)
{
将物品i包含在当前方案中(设置物品i为包含状态);
if(i<n-1></n-1>try(i+1,tw+物品i的重量,tv);
else
//又一个完整方案,因为它比前面的方案好,以它作为最佳方案
以当前方案为最佳方案保存
恢复物品i不包含状态;
}
//考虑物品i不包含在当前方案中的可能性
if(不包含物品i仅是可考虑的)
{
if(i<n-1></n-1>try(i+1,tw,tv-物品i的价值);
else
//又一个完整方案,因为它比前面的方案好,以它作为最佳方案
以当前方案为最佳方案保存
}
}
*/
#define N 100
int limitW,//限制的总重量
totalV,//全部物品的总价值
maxV;//所选方案的最大总价值
int option[N],//解的选择标志
curoption[N];//当前解的选择标志
struct Goods//物品数据结构
{
int weight;
int value;
};
Goods array[N];
int n;//物品种数
//参数定义
//i:物品编号
//tw:当前选择已达到的物品总重量和
//tv:本方案可能达到的物品总价值
void Find(int i,int tw,int tv)
{
int k;
//考虑物品i包含在当前方案中的可能性
if(tw+array[i].weight {//包含物品i是可接受的
curoption[i] = 1;//将物品i包含在当前方案中(设置物品i为包含状态);
if(i<n-1></n-1>Find(i+1,tw+array[i].weight,tv);
else
{//又一个完整方案,因为它比前面的方案好,以它作为最佳方案
for(k=0;k<n></n>option[k] = curoption[k];
maxV = tv;
}
curoption[i] = 0;//恢复物品i不包含状态
}
//考虑物品i不包含在当前方案中的可能性
if(tv-array[i].value > maxV)
{
if(i<n-1></n-1>Find(i+1,tw,tv-array[i].value);
else
{//又一个完整方案,因为它比前面的方案好,以它作为最佳方案
for(k=0;k<n></n>option[k] = curoption[k];
maxV = tv-array[i].value;
}
}
}
void BackPack_Problem()
{
int k,w,v;
printf("输入物品种数\n");
scanf("%d",&n);
printf("输入各物品的重量及价值\n");
for(totalV = 0,k=0;k<n></n>{
scanf("%d%d",&w,&v);
array[k].weight = w;
array[k].value = v;
totalV += v;
}
printf("输入限制的重量\n");
scanf("%d",&limitW);
maxV = 0;
for(k=0;k<n></n>curoption[k] = 0;
Find(0,0,totalV);
for(k=0;k<n></n>if(option[k])
printf("%4d",k+1);
printf("总价值 = %d\n",maxV);
printf("\n\n应用程序正在运行......\n");
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935647
相关推荐
背包问题算法及并行源程序 背包问题算法及并行源程序
实现背包算法,并应用到一些基本的背包问题解答中。。。。
01背包问题算法的C++实现。 knapsack.cpp + knapsack.h
包含了背包问题的所有算法的解法
背包问题算法Java实现,实现了背包问题得到最大的价值,有压栈
背包问题算法代码C语言实现
python解决背包 问题算法课程作业
python动态规划背包问题算法-01背包问题(动态规划算法) 给定 N 种物品和⼀个容量为 V 的背包,物品 i 的体积是 wi,其价值为 ci 。 (每种物品只有⼀个) 问:如何选择装⼊背包的物品,使得装⼊背包中的物品的总...
一个很好的背包问题算法,里面包含有详细的解析,及原理解释,另外还有生成文件,对于研究算法的朋友有一定的帮助
0-1背包问题算法研究,武燕,谢刚,0-1背包问题(Knapsack Problem,简称KP)是算法设计分析中的经典问题,具有广泛的实际应用背景。本文首先介绍了什么是0-1背包问题,接着
动态规划(DP)——背包问题算法详解[背包九讲]
背包问题算法设计.docx
连续背包问题算法设计.docx
贪心算法实现背包问题算法设计与分析实验报告.doc
用遗传算法解决多维背包问题,采用java代码。用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码。
解决01背包问题算法比较.ppt.ppt
0-1 背包问题算法研究1.doc
算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现 算法...
解决背包问题算法比较PPT学习教案.pptx
给定n个物品和一个容量为C的背包,物品i的重量是wi,其价值为vi。背包问题是如何选择装入背包的物品,使得装入背包中的物品总价值最大?(物品可以分割)