[数据结构与算法]动态规划算法解决经典背包问题

动态规划算法

应用场景：背包问题
条件：

• 1）要求达到的目标为装入的背包的总价值最大，并且重量不超出
• 2）要求装入的物品不能重复
  算法介绍：
  1）动态规划的核心思想：将大问题分为小问题进行解决，从而一步步获取最优解的处理方法
  2）算法与分治算法类似，其基本思想也是将带求解的问题分解成若干个小问题，先求子问题，然后从这些子问题的解得到原问题的解；
  3）与分治法不同的是，适合于动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一阶段的求解是建立在上一阶段的解的基础上，进行进一步的求解）
  4）动态规划可以通过填表的方式来逐步推进，得到最优解。

动态规划解决背包问题01

01背包：即每个物品最多放一个

public class Demon1 {
	public static void main(String[] args) {
		int[] w= {1,4,3};  //物品的重量
		int[] val= {1500,3000,2000};  //物品的价值
		int m=4;  //背包的容量
		int n=val.length;  //物品的个数
		
		//创建二维数组
		//v[i][j]表示在前i个物品中能够装入容量为j的背包的最大价值
		int[][] v=new int[n+1][m+1];
		//记录商品情况
		int[][] path=new int[n+1][m+1];
		//初始化第一行和第一列，
		for(int i=0;i<v.length;i++) {
			v[i][0]=0;  //将第一列设置为0 
		}
		for(int i=0;i<v[0].length;i++) {
			v[0][i]=0;  //将第一行设置为0
		}
		
		for(int i=1;i<v.length;i++) {
			for(int j=1;j<v[0].length;j++) {
				//公式
				if(w[i-1]>j) {
					v[i][j]=v[i-1][j];
				}else {
					//公式需调整
//					v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
//					v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
					//记录商品情况
					if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]) {
						v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
						//情况记录到path
						path[i][j]=1;
					}else {
						v[i][j]=v[i-1][j];
					}
				}
			}
		}
		//目前的情况
		for(int i=0;i<v.length;i++) {
			for(int j=0;j<v[i].length;j++) {
				System.out.print(v[i][j]+" ");
			}
			System.out.println();
		}
		//输出最后放入的那些商品
		//遍历path
//		for(int i=0;i<path.length;i++) {
//			for(int j=0;j<path[i].length;j++) {
//				if(path[i][j]==1) {
//					System.out.printf("第%d个商品放入背包\n",i);
//				}
//			}
//		}
		
		int i=path.length-1; //行的最大下标
		int j=path[0].length-1; //列的最大下标
		while(i>0&&j>0) {
			if(path[i][j]==1) {
				System.out.printf("第%d个商品放入背包\n",i);
				j-=w[i-1];
			}
			i--;
		}
		
	}
	
}

输出结果：