文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 分别用回溯法和分支限界法求解0-1背包问题
侵权投诉

分别用回溯法和分支限界法求解0-1背包问题

一、 实验题目:

分别用回溯法和分支限界法求解0-1背包问题

二、 实验内容:

0-1背包问题: 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?

在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。

三、 程序源代码:

A:回溯法:

// bag1.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream.h>

#define MaxSize 100 //最多物品数

int limitw; //限制的总重量

int maxwv=0; //存放最优解的总价值

int maxw;

int n; //实际物品数

int option[MaxSize]; // 存放最终解

int op[MaxSize]; //存放临时解

struct {

int weight;

int value;

}a[MaxSize]; //存放物品数组

void Knap( int i, int tw, int tv) //考虑第i个物品

{

int j;

if(i>=n) //找到一个叶子结点

{

if (tw<=limitw && tv>maxwv) //找到一个满足条件地更优解,保存它

{

maxwv=tv; maxw=tw;

for(j=0;j<n;j++) option[j]=op[j];

}

}

else

{

op[i]=1; //选取第I个物品

Knap(i+1,tw+a[i].weight, tv+a[i].value);

op[i]=0; //不选取第I个物品,回溯

第1页

你可能喜欢

  • 拓扑排序算法
  • 背包问题
  • 背包算法
  • 规划报告
  • 算法分析与设计试题
  • 计算机算法
  • 贪心算法
  • 分支界限法

热门文档

相关文档

  • 回溯法和分支限界法解决0-1背包题

    回溯法和分支限界法解决0-1背包题_计算机软件及应用_IT/计算机_专业资料。用回溯法和分支限界法解决0-1背包题,并对两种算法进行分析比较。...

  • 回溯法、分支限界法解0-1背包问题(计算机算法设计与分...

    二、主要实验内容及要求: 1.要求分别用回溯法和分支限界法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 三、实验...

  • 分支界限法解0-1背包问题实验报告

    实验5 一 、实验要求 分支界限法解 分支界限法解 0-1 背包问题 1.要求用分支界限法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组;...

  • 第五组分支限界法(0-1背包问题)

    分支限界法实现0-1背包问... 1页 免费 分别用回溯法和分支限界... 8页 ... 设计内容 1. 任务描述 1) 算法简介 也是在问题的解空间上搜索问题解的算法...

  • 蛮力法、动态规划法、回溯法和分支限界法求解01背包问题

    一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解 0/1 背包问题。 注:0/1 背包问题:给定 n 种物品和一个容量为 C 的背包,物品 i 的重量...

  • 分支限界法解01背包问题

    分支限界法解 01 背包问题学院:网研院 一、 分支限界法原理 姓名:XXX 学号:2013XXXXXX 分支限界法类似于回溯法, 也是在问题的解空间上搜索问题解的算法。一 般...

  • 0-1背包问题(回溯法)

    (原创精品)0-1背包问题(... 3页 免费 回溯法解0-1背包问题 3页 免费 回溯法-0-1背包问题 2页 免费 分别用回溯法和分支限界... 8页 2下载券...

  • 算法0-1背包问题

    1.要求分别用回溯法和分支限界法求解 0-1 背包问题; 2.要求交互输入背包容量,物品重量数组,物品价值数组; 3.要求显示结果。 二、实验方案在选择装入背包的物品...

  • 求解0-1背包问题算法综述

    关键词:0-1 背包问题;动态规划法;递归法;回溯法;贪心算法 中图分类号:TP312...到目前为止,求解 0-1 背包问题的方法很多。 精确算法有 分支限界法 、动态...

  • 0-1背包问题的不同求法

    分支限界法实现0-1背包 5页 免费 分别用回溯法和分支限界... 8页 2下载...0-1 背包问题的求解 /* 0-1 背包问题具有最优子结构性质和子问题重叠性质,...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email