数据结构与算法(九)动态规划

特点

  • 局部最优解:也就是它会有一个最优子结构
  • 子问题可以重复
  • 状态转移方程:通过把问题分成很多小阶段一段段的转移。从而得出最优解.状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程,那动态规划问题基本上就解决一大半了,翻译成代码非常简单。但是很多动态规划问题的状态本身就不好定义,状态转移方程也就更不好想到。

问题

背包问题
小偷去某商店盗窃,背有一个背包,容量是5kg,现在有以下物品(物品不能切分,且只有一个),请问小偷应该怎么拿才能得到最大的价值?
|物品|重量|价值|
|-------|-------|-------|
|物品1|1kg| 6元|
|物品2|2kg| 10元|
|物品3|4kg| 12元|

我们把5kg的袋子,拆分成1kg,1kg这样子计算,里面的表格就表示当前重量下能装的最多的钱。表格的数列就表示是要装的物品

物品1kg2kg3kg4kg5kg
加入物品166666
加入物品261010+6=1610+6=1616
加入物品3610161618

加入物品2时,袋子当前为1kg 的容量时,我们发现物品2装不进去。那我们应该取多少呢?是不是只要取物品进来时1kg最大钱?,当袋子为2kg时,我们发现物品2可以装下去,此时可以得到10块钱,比之前物品1进来时价值6大,所以我们选择大的这个10,而不是6.此时袋子还剩0kg可以装。

袋子为3kg时,我们还是可以装下这个物品2,得到10块,袋子还剩下1kg。10+1kg能装的东西(10+6=16)。
物品3来了,袋子为4kg时,物品3可以转进来,得到12块钱,袋子还剩0kg。但我们发现不装物品3 还能得到16。
物品3来了,袋子为5kg时,物品3可以转进来,得到12块钱,袋子还剩1kg。那么装了物品3就能得到12+6=18块钱
我们发现不装物品3得到16,比18小,所以决定装。

上面这一个递推过程总结起来就是一个东西------状态转移方程:
能装的时候 每次和上面的比较,大我就装,否则就不装。

代码

public static void main(String[] args) {
		
		int value [] ={60,100,120};
		int weigth[] = {10,20,40};	
		
		int w = 50;
		int n = 3;
		int dp[][] = new int[n+1][w+1];		//n表示是物品,w表示重量,初始化全是0
		
		for(int i = 1; i<= n; i++){	//每次加的物品
			for(int cw = 1 ; cw <= w ; cw ++){		//分割的背包
				if(weigth[i - 1] <= cw){		//表示这个物品可以装进去
					dp[i][cw] = Math.max(
							value[i-1] + dp[i-1][cw-weigth[i-1]],
							dp[i-1][cw]
							);
				}else{
					dp[i][cw] = dp[i-1][cw];	//不能装
				}
			}
		}
		System.out.println(dp[n][w]);
		
	}

购物车问题
双十一马上就要来了,小C心目中的女神在购物车加了N个东西,突然她中了一个奖可以清空购物车5000元的东西(不能找零),每个东西只能买一件,那么她应该如何选择物品使之中奖的额度能最大利用呢?

public class ShoppingCart {

    public static void greedy(int[] money, int maxMoney) {
        //定义规划表格
        //money = 1, 2, 3, 4, 5, 6, 7, 8
        //maxMoney = 10
        //输出第几个物品
        int[][] dp = new int[money.length + 1][maxMoney + 1];
        for (int i = 0; i < money.length; i++) {
            for (int j = 1; j <= maxMoney; j++) {
                if (money[i] <= j) {
                    dp[i + 1][j] = Math.max(money[i] + dp[i][j - money[i]], dp[i][j]);
                } else {
                    dp[i + 1][j] = dp[i][j];
                }
            }
        }
        System.out.println(dp[money.length][maxMoney]);
        int i = money.length;
        int surplus = maxMoney;
        System.out.print("取得组合是:");
        while (i > 0) {
            if (dp[i][surplus] > dp[i - 1][surplus]) {
                //说明取了
                System.out.print(money[i - 1]+ "  ");
                //推导组合
                //取了之后的剩余量
                surplus = surplus - money[i - 1];
            } else {
                //没取,取得是上一组
            }
            i--;
        }

    }

    public static void main(String[] args) {
        int[] money = { 7, 8, 4, 5};
        greedy(money, 10);

    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×