内容简介：动态规划算法简介：
动态规划算法简介： 动态规划算法
背包问题：
有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]);
}
}
程序运行结果：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Head First Python
Paul Barry / O'Reilly Media / 2010-11-30 / USD 49.99
Are you keen to add Python to your programming skills? Learn quickly and have some fun at the same time with Head First Python. This book takes you beyond typical how-to manuals with engaging images, ......一起来看看 《Head First Python》 这本书的介绍吧!
