实 验 报 告

课程名称：  算法设计与分析  实验名称：解0-1背包问题

任课教师：     王锦彪       专    业：计算机应用技术

班    级:      20##         学    号：   112015      

姓    名：     严焱心       完成日期： 20##年11月   

一、实验目的：

掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。

…… …… 余下全文

0-1背包问题实验报告

一．问题描述

1. 给定n种物品和一个背包。物品i的重量是w[i]，其价值为v[i]，背包容量为c。 问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

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

二．问题规模

1．物品数目：n=50，

2．背包容量：c=1000，

3．每个物品重量分别为：

{220,208,198,192,180,180,165,162,160,158,

155,130,125,122,120,118,115,110,105,101,

100,100,98,96,95,90,88,82,80,77,

75,73,70,69,66,65,63,60,58,56,

50,30,20,15,10,8,5,3,1,1}

4． 每个物品价值分别为：

{80,82,85,70,72,70,66,50,55,25,

50,55,40,48,50,32,22,60,30,32,

40,38,35,32,25,28,30,22,50,30,

…… …… 余下全文

0-1背包问题实验报告

一：0-1背包问题

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

在选择装入背包的物品时，对每种物品i只有两种选择，装入或者不装入背包。不能将物品i多次装入，也不能装入部分的物品i。因此，该问题被称为0-1背包问题。

本次针对0-1背包问题的实验，主要使用动态规划的方法、贪心算法、回溯法以及分支限界法。

测试用例为：

n=50，

c=1000，

每个物品重量为

{220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1,1}

每个物品价值为

{80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1} 下面将分别谈论。

…… …… 余下全文

实验4   回溯法解0-1背包问题

一、实验要求

1．要求用回溯法求解0-1背包问题；

2．要求交互输入背包容量，物品重量数组，物品价值数组；

3．要求显示结果。

二、实验仪器和软件平台

仪器 ：带usb接口微机

软件平台：WIN-XP  +  VC++6.0

三、实验源码

#include "stdafx.h"

#include<iostream>

#include<cstdio>

#include<conio.h>

#include<iomanip>

using namespace std;

template<class ty>

class Knap 

{

public:

    friend void Init();

    friend void Knapsack();

    friend void Backtrack(int i);

…… …… 余下全文

算法设计与分析

实验报告

—0/1背包问题

-

【问题描述】

      给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

【问题分析】

0/1背包问题的可形式化描述为：给定C>0, >0, >0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。

                                             

…… …… 余下全文

 西安理工大学实验报告

                                                        第 1 页（共 2 页）

课    程：                                  实验日期：         年    月   日

…… …… 余下全文

  姓名：

  学号：

  班级：

"0-1"背包问题的动态规划算法

一、   实验目的与要求：

熟悉C/C++语言的集成开发环境；

通过本实验加深对贪心算法、动态规划和回溯算法的理解。

二、   实验内容：

掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。

三、     实验程序：

#include"stdio.h"

int n=5;

int w[]={0,3,2,1,4,5};

int v[]={0,25,20,15,40,50};

int x[5];

int V[6][7];

int C=6;

void main(void)

{

    int i,j;

    for(i=0;i<=n;i++)

        V[i][0]=0;

…… …… 余下全文

数学与计算机学院数据结构实验报告

年级 2008级 学号 姓名 成绩

专业 数学类 实验地点 主楼402 指导教师 成 实验项目背包问题实验报告 实验日期 2009-11-25

一、 实验题目

设有n件物品，其重量分别为W1,W2,...,Wn，有一背包容量为T，求从n

件物品取若干件，他们的重量和恰好等于背包容量T的所有解。

二、需求分析

本程序使用的开发工具为C++语言，旨在解决背包问题。

三、程序流程图

（略）

四、数据结构及算法描述

#ifndef LJL

#define LJL

#define N100 100

typedef struct NUM{ //计数数组

typedef struct node{ //定义存储栈的节点

int weight; int weight[N100]; int num; }MNUM;

#endif

#include "stdafx.h"

#include "背包问题.h"

…… …… 余下全文