动态规划例题

栏目: 编程工具 · 发布时间: 5年前

内容简介:动态规划算法简介:

动态规划算法简介: 动态规划算法

背包问题:

有n个重量和价值分别为wi,vi的物品,从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。

1≤n≤100
1≤wi,vi≤100
1≤W≤10000

输入:

n=4
(w,v)={(2,3),(1,2),(3,4),(2,2)}
W=5

输出:

7(选择第0,1,3号物品)

因为对每个物品只有选和不选两种情况,所以这个问题称为01背包。

Java代码示例:

import java.util.Arrays;

public class 背包问题 {
	static int[] w = {2, 1, 3, 2};//重量表
	static int[] v = {3, 2, 4, 2};//价值表
	static int n = 4;//物品数量
	static int W = 5;//背包的承重极限
	static int[][] rec = new int[n][W + 1];
	public static void main(String[] args) {
		int ww = W;
		int ans = dfs(0, ww);
		System.out.println(ans);
		for(int i = 0; i < n; i++) {
			Arrays.fill(rec[i], -1);
		}
		ww = W;
		ans = dfs1(0, ww);
		System.out.println(ans);

	}
	//利用dfs来做,每种情况都试试
	private static int dfs(int i, int ww) {
		if(ww <= 0) return 0;
		if(i == n) return 0;
		int v2 = dfs(i + 1, ww); //不选择当前物品
		if(ww >= w[i]) { 
			int v1 = v[i] + dfs(i + 1, ww - w[i]);//选择当前物品
			return Math.max(v1, v2);
		}else {
			return v2;
		}
	}
	
	//记忆性递归,加快计算速度
	private static int dfs1(int i, int ww) {
		if(ww <= 0) return 0;
		if(i == n) return 0;
		//1. 查询
		if(rec[i][ww] >= 0) {
			return rec[i][ww];
		}
		int v2 = dfs1(i + 1, ww); //不选择当前物品
		int ans;
		if(ww >= w[i]) { 
			int v1 = v[i] + dfs1(i + 1, ww - w[i]);//选择当前物品
			ans = Math.max(v1, v2);
		}else {
			ans = v2;
		}
		//2.记录:
		rec[i][ww] = ans;//备忘录
		return ans;
	}
}

程序运行结果:

背包问题动态规划解法:

解题思路:

动态规划例题

Java代码示例:

public class 背包问题dp {
	static int[] w = {2, 1, 3, 2};//重量表
	static int[] v = {3, 2, 4, 2};//价值表
	static int n = 4;//物品数量
	static int W = 5;//背包的承重极限
	public static void main(String[] args) {
		dp();
	}
	
	
	public static void dp() {
		int[][] dp =  new int[n][W+1];
		//初始化dp表第一行
		for(int i = 0; i < W + 1; i++) {
			if(i >= w[0]) {
				dp[0][i] = v[0];
			}
		}
		//其他行
		for(int i = 1; i < n; i++) {
			//j是列,也是背包剩余的容量
			for(int j = 0; j < W + 1; j++) {
				if(j >= w[i]) {
					int v1 = v[i] + dp[i-1][j-w[i]];//要的话
					int v2 = dp[i-1][j];//不要这个
					dp[i][j] = Math.max(v1, v2);
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		System.out.println(dp[n - 1][W]);
	}
}

程序运行结果:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

你不知道的JavaScript(中卷)

你不知道的JavaScript(中卷)

[美] Kyle Simpson / 单业、姜南 / 人民邮电出版社 / 2016-8 / 79.00元

JavaScript这门语言简单易用,很容易上手,但其语言机制复杂微妙,即使是经验丰富的JavaScript开发人员,如果没有认真学习的话也无法真正理解。本套书直面当前JavaScript开发人员不求甚解的大趋势,深入理解语言内部的机制,全面介绍了JavaScript中常被人误解和忽视的重要知识点。本书是其中卷,主要介绍了类型、语法、异步和性能。一起来看看 《你不知道的JavaScript(中卷)》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具