算法设计与分析实验报告—01背包问题(共6页).docx

精选优质文档-倾情为你奉上算法设计与分析实验报告0/1背包问题-【问题描述】给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定C0, 0, 0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。【算法设计】设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下： maxm( i+1, j ), m( i+1, j-)+ m( i, j )=m(i+1,j) m(n,j)=0 【算法实现】#include #include