内容简介：动态规划算法简介：
动态规划算法简介： 动态规划算法
背包问题：
有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]);
}
}
程序运行结果：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Complexity and Approximation
G. Ausiello、P. Crescenzi、V. Kann、Marchetti-sp、Giorgio Gambosi、Alberto M. Spaccamela / Springer / 2003-02 / USD 74.95
This book is an up-to-date documentation of the state of the art in combinatorial optimization, presenting approximate solutions of virtually all relevant classes of NP-hard optimization problems. The......一起来看看 《Complexity and Approximation》 这本书的介绍吧!
