用动态规划解0-1背包问题.docxVIP

实验一 用动态规划解0-1背包问题 实验目的与要求 1、掌握动态规划算法求解问题的一般特征和步骤 2、使用动态规划法编程求解0/1背包问题。 实验内容 0-1背包问题(knapsack problem)：某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为C，C为一非负 数。目标是如何选择装入背包的物品使装入背包的物品总价值最大，所选商品 的一个可行解即所选商品的序列如何。背包问题与0-1 背包问题的不同点在 于：在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品 的全部。 三、问题描述 给定n和物品和一人背包，物品i的重量是wi，其价值为vi，问：如何选择装 入背包的物品，使得装入背包的物品的总价值最大。 举例: 若商店一共有5类商品，重量分别为：34789，价值分别为：45101113，则所选商品的最大价值为24， 所选商品的一个序列为0 0 0 1 1。 四、问题分析与算法设计 动态规划原理：动态规划是一种将问题实例分解为更小的、相似的子问题并存 储子问题的解而避免计算重复的子问题以解决最优化问题的算法策略。 动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问 题呈现大量的重复。动态规划法的关键就在于：对于重复出现的子问题，只在 第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用而不必 重新求解。 实验结果 源程序： #includeiostream using namespace std; void knapsack(int m[30][30],int w[30],int v[30],int n,int C) { for(int i = 0; i = C; i ++) m[0][i] = 0; for(int i = 1; i = n; i ++) { m[i][0] = 0; for(int j = 1; j = C; j ++) { if(w[i] = j) { if(v[i] + m[i - 1][j - w[i]] m[i - 1][j]) m[i][j] = v[i] + m[i - 1][j - w[i]]; else m[i][j] = m[i - 1][j]; }else m[i][j] = m[i - 1][j]; } } } void traceback(int m[30][30],int x[30],int w[30],int n,int C) { for(int k = n; k = 2; k --) { if(m[k][C] == m[k-1][C]) x[k] = 0; else { x[k] = 1; C = C - w[k]; } } x[1] = m[1][C] ? 1 : 0; } int main() { int m[30][30] , w[30] , v[30] , x[30] , C , n; cout请输入物品的总个数：; cinn; cout请输入背包的总容量：; cinC; coutendl; for(int i = 1; i = n; i ++) { cout请输入第i个物品的重量：; cin w[i]; } coutendl; for(int i = 1; i = n; i ++) { cout请输入第i个物品的价值：; cin v[i]; } knapsack(m, w, v, n, C); traceback(m, x, w, n, C); cout最优解为：endl; for(int i = 1; i = n; i ++) coutx[i] ; coutendl背包中物品的最大价值是：endl; coutm[n][C]endl; system(pause); return 0; }