下载文档原格式
动态规划——01背包问题⼀、最基础的动态规划之⼀01背包问题是动态规划中最基础的问题之⼀，它的解法完美地体现了动态规划的思想和性质。
01背包问题最常见的问题形式是：给定n件物品的体积和价值，将他们尽可能地放⼊⼀个体积固定的背包，最⼤的价值可以是多少。
我们可以⽤费⽤c和价值v来描述⼀件物品，再设允许的最⼤花费为w。
只要n稍⼤，我们就不可能通过搜索来遍查所有组合的可能。
运⽤动态规划的思想，我们把原来的问题拆分为⼦问题，⼦问题再进⼀步拆分直⾄不可再分（初始值），随后从初始值开始，尽可能地求取每⼀个⼦问题的最优解，最终就能求得原问题的解。
由于不同的问题可能有相同的⼦问题，⼦问题存在⼤量重叠，我们需要额外的空间来存储已经求得的⼦问题的最优解。
这样，可以⼤幅度地降低时间复杂度。
有了这样的思想，我们来看01背包问题可以怎样拆分成⼦问题：要求解的问题是：在n件物品中最⼤花费为w能得到的最⼤价值。
显然，对于0 <= i <= n,0 <= j <= w，在前i件物品中最⼤花费为j能得到的最⼤价值。
可以使⽤数组dp[n + 1][w + 1]来存储所有的⼦问题，dp[i][j]就代表从前i件物品中选出总花费不超过j时的最⼤价值。
可知dp[0][j]值⼀定为零。
那么，该怎么递推求取所有⼦问题的解呢。
显⽽易见，要考虑在前i件物品中拿取，⾸先要考虑前i - 1件物品中拿取的最优情况。
当我们从第i - 1件物品递推到第i件时，我们就要考虑这件物品是拿，还是不拿，怎样收益最⼤。
①：⾸先，如果j < c[i]，那第i件物品是⽆论如何拿不了的，dp[i][j] = dp[i - 1][j];②：如果可以拿，那就要考虑拿了之后收益是否更⼤。
拿这件物品需要花费c[i]，除去这c[i]的⼦问题应该是dp[i - 1][j - c[i]]，这时，就要⽐较dp[i - 1][j]和dp[i - 1][j - c[i]] + v[i]，得出最优⽅案。
0/1背包问题1. 问题描述给定一个载重量为m，n个物品，其重量为w i，价值为v i，1<=i<=n，要求:把物品装入背包，并使包内物品价值最大2. 问题分析在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。
循环变量i，j意义：前i个物品能够装入载重量为j的背包中(n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值若w[i]>j，第i个物品不装入背包否则，若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）计算最大价值的动态规划算法如下：//计算for(i=1;i<row;i++){for(j=1;j<col;j++){//w[i]>j,第i个物品不装入背包value[i][j]=value[i-1][j];//w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值int temp=value[i-1][j-w[i]]+v[i];if(w[i]<=j && temp>value[i][j])value[i][j]=temp;}}即该段程序完成以下n个阶段：1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值。
n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值3. 问题求解确定装入背包的具体物品，从value[n][m]向前逆推：若value[n][m]>value[n-1][m]，则第n个物品被装入背包，且前n-1个物品被装入载重量为m-w[n]的背包中否则，第n个物品没有装入背包，且前n-1个物品被装入载重量为m的背包中以此类推，直到确定第一个物品是否被装入背包为止。
动态规划算法--01背包问题基本思想：动态规划算法通常⽤于求解具有某种最优性质的问题。
在这类问题中，可能会有许多可⾏解。
每⼀个解都对应于⼀个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若⼲个⼦问题，先求解⼦问题，然后从这些⼦问题的解得到原问题的解。
与分治法不同的是，适合于⽤动态规划求解的问题，经分解得到⼦问题往往不是互相独⽴的（即下⼀个⼦阶段的求解是建⽴在上⼀个⼦阶段的解的基础上，进⾏进⼀步的求解）。
若⽤分治法来解这类问题，则分解得到的⼦问题数⽬太多，有些⼦问题被重复计算了很多次。
如果我们能够保存已解决的⼦问题的答案，⽽在需要时再找出已求得的答案，这样就可以避免⼤量的重复计算，节省时间。
我们可以⽤⼀个表来记录所有已解的⼦问题的答案。
不管该⼦问题以后是否被⽤到，只要它被计算过，就将其结果填⼊表中。
这就是动态规划法的基本思路。
具体的动态规划算法多种多样，但它们具有相同的填表格式。
应⽤场景：适⽤动态规划的问题必须满⾜最优化原理、⽆后效性和重叠性。
1、最优化原理（最优⼦结构性质）最优化原理可这样阐述：⼀个最优化策略具有这样的性质，不论过去状态和决策如何，对前⾯的决策所形成的状态⽽⾔，余下的诸决策必须构成最优策略。
简⽽⾔之，⼀个最优化策略的⼦策略总是最优的。
⼀个问题满⾜最优化原理⼜称其具有最优⼦结构性质。
2、⽆后效性将各阶段按照⼀定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态⽆法直接影响它未来的决策，⽽只能通过当前的这个状态。
换句话说，每个状态都是过去历史的⼀个完整总结。
这就是⽆后向性，⼜称为⽆后效性。
3、⼦问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。
其中的关键在于解决冗余，这是动态规划算法的根本⽬的。
动态规划实质上是⼀种以空间换时间的技术，它在实现的过程中，不得不存储产⽣过程中的各种状态，所以它的空间复杂度要⼤于其它的算法。
背包问题（Knapsackproblem）采⽤动态规划求解问题说明:假设有⼀个背包的负重最多可达8公⽄，⽽希望在背包中装⼊负重范围内可得之总价物品，假设是⽔果好了，⽔果的编号、单价与重量如下所⽰：李⼦4KGNT$45001苹果5KGNT$57002橘⼦2KGNT$22503草莓1KGNT$1100解法背包问题是关于最佳化的问题，要解最佳化问题可以使⽤「动态规划」（Dynamicprogramming），从空集合开始，每增加⼀个元素就先求出该阶段的最佳解，直到所有的元素加⼊⾄集合中，最后得到的就是最佳解。
下⾯我们看下代码:/*问题:假设有⼀个背包的负重最多可达8公⽄，⽽希望在背包中装⼊负重范围内可得之总价物品算法说明:采⽤动态规划,在当前阶段求解出最好的解,如此反复⽇期:2013/8/18张威*/#include <iostream>#include <time.h>using namespace std;#define MAXSIZE 8//定义全局变量char name[5][5] = {"李⼦","苹果","橘⼦","草莓","甜⽠"};//⽔果名称int wight[5] = {4,5,2,1,6};//单个⽔果所占⽄数int price[5] = {4500,5700,2250,1100,6700};//单个⽔果的价值int perkg_price[5];//每⽄⽔果的价钱int perkg_num[5] = {0,1,2,3,4};void GetNmae(int num){for (int i = 0;i <= 4;i++){cout<<name[num][i];}}void GetBestAnswer(int currentwigh){//判断递归终⽌条件if (currentwigh >= MAXSIZE){cout<<"包裹已经满了,⽆法再装进东西"<<endl;}else{//check⽤来表证到底剩下来的物品⾥⾯还有没有能装进去背包⾥的bool check = true;int i = 0;for (;i <= 4;i++){//若是没有进⼊到这个条件内,说明剩下来的物品的重量都超过了背包剩余重量,到此结束.否则i就代表当前所能选中的最优解if (wight[perkg_num[i]] <= MAXSIZE-currentwigh){check = false;break;}}if (check == true){cout<<"已经装不进去任何⽔果了"<<endl;}else{//得到最优解,并且将当前重量增加,进⼊下⼀次递归currentwigh += wight[perkg_num[i]];cout<<"购买了";GetNmae(perkg_num[i]);cout<<endl;GetBestAnswer(currentwigh);}}}int main(){//计算出每⽄⽔果的价钱,便于动态规划时求出当前最佳解for (int i = 0;i <= 4;i++){perkg_price[i] = price[i] / wight[i];}//对perkg_num进⾏排序,同时保证单价和perkg_num之间的⼀⼀对应关系.即两个数组要同时变化//采⽤的是冒泡排序,在元素进⾏交换时perkg_num和perkg_price同时变化for (int i = 0;i <= 3;i++){for (int j = i;j <= 3;j++){if (perkg_price[j] < perkg_price[j+1]){int temp1 = perkg_price[j];int temp2 = perkg_num[j];perkg_price[j] = perkg_price[j+1];perkg_price[j+1] = temp1;perkg_num[j] = perkg_num[j+1];perkg_num[j+1] = temp2;}}}//开始计算求解GetBestAnswer(0);return0;}背包问题在这⾥,算法的主要思想有两个:1.通过冒泡排序得到⼀个单价表,并将物品的ID与之配对起来.这样我们在每次的递归中通过ID找到物品的相应属性,筛选出当前步骤的最优解出来2.通过递归,传递当前的重量,得到还剩余的重量,根据前⾯的单价表,筛选出可选的最优解,然后将重量变化进⼊下⼀次递归.这是最⼤空间为8的运⾏结果: 这是最⼤空间为29的运⾏结果:下⾯附上指导书上⾯的代码:#include <stdio.h>#include <stdlib.h>#define LIMIT 8// 重量限制#define N 5// 物品种类#define MIN 1// 最⼩重量struct body {char name[20];int size;int price;};背包负重12345678value110225335450570680795905item323０1323背包负重12345678value110225335450570680795905item323０1323typedef struct body object;int main(void) {int item[LIMIT+1] = {0};int value[LIMIT+1] = {0};int newvalue, i, s, p;object a[] = {{"李⼦", 4, 4500}, {"苹果", 5, 5700},{"橘⼦", 2, 2250},{"草莓", 1, 1100},{"甜⽠", 6, 6700}};for(i = 0; i < N;i++) {for(s = a[i].size; s <= LIMIT;s++) { p = s - a[i].size;newvalue = value[p] + a[i].price;if(newvalue > value[s]) {// 找到阶段最佳解value[s] = newvalue;item[s] = i;}}}printf("物品\t价格\n");for(i = LIMIT;i >= MIN;i = i - a[item[i]].size) {printf("%s\t%d\n",a[item[i]].name, a[item[i]].price);}printf("合计\t%d\n", value[LIMIT]);return0;}Javaclass Fruit {private String name;private int size;private int price;public Fruit(String name,int size, int price){ = name;this.size = size;this.price = price;}public String getName(){return name;}public int getPrice(){return price;}public int getSize() {return size;}}public class Knapsack {public static void main(String[] args){final int MAX = 8;final int MIN = 1;int[] item = new int[MAX+1];int[] value = new int[MAX+1];Fruit fruits[] = {new Fruit("李⼦", 4, 4500),new Fruit("苹果", 5, 5700),new Fruit("橘⼦", 2, 2250),new Fruit("草莓", 1, 1100),new Fruit("甜⽠", 6, 6700)};for(int i = 0; i < fruits.length;i++) {for(int s = fruits[i].getSize(); s <= MAX;s++){int p = s - fruits[i].getSize();int newvalue = value[p] +fruits[i].getPrice();if(newvalue > value[s]) {// 找到阶段最佳解value[s] = newvalue;item[s] = i;}}}System.out.println("物品\t价格");for(int i = MAX;i >= MIN;i = i - fruits[item[i]].getSize()) {System.out.println(fruits[item[i]].getName()+"\t" + fruits[item[i]].getPrice());}System.out.println("合计\t" + value[MAX]);}}指导书上⾯的代码我居然没想到使⽤结构体,失策失策,都没⽤什么⾼级点的数据结构,看起来貌似很复杂的样⼦.明天再看。
