01背包问题
1. 问题描述：
有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背包）
2. 我们发现使用普通的递归或者深搜来解决的时候会发现如果数据量大的话那么耗时是比较大的，其中有可能在递归的过程中有些子问题是重复求解的，例如在递归的时候当前求解出f( n - 2 )，然后在后面递归的时候也求解f(n - 2)那么这个就是重复子问题的重复求解了，假如我们能够在递归的时候求解一次子问题之后然后再次遇到重复的子问题的时候就不用再求解下去了，这个时候就要使用到我们的记忆性的递归了，把中间结果记录下来，在递归之前看一下这个子问题是不是之前求解过，假如之前求解过那么后面的时候直接返回结果就好了，这就是：计算之前先查询，计算之后做保存的操作
这道题目由于涉及到可以选择当前物品的下标，可以选择的剩下物品的质量这两个变量，所以我们可以使用二维数组这个数据结果来保存中间的结果，这样就不会重复的子问题重复求解了
只需要把简单的递归的代码改动一下就可以了，增加的代码只是保存中间结果的问题，所以这种递归也叫记忆性的递归（记忆性的深搜）
3. 具体的代码如下：
import java.util.Arrays;
import java.util.scanner;
import static java.lang.Math.max;
public class Main{
static int rec[][];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextint();
int w[] = new int[n];
int v[] = new int[n];
for(int i = 0; i <n; i++){
w[i] = sc.nextInt();
}
for(int i = 0; i <n; i++){
v[i] = sc.nextInt();
}
int W = sc.nextInt();
rec = new int[n][W + 1];
for(int i = 0; i < n; i++){
Arrays.fill(rec[i], -1);
}
int res = dfs(w, v, 0, n, W);
System.out.println(res);
sc.close();
}
private static int dfs(int[] w, int[] v, int cur, int n, int W){
if(cur == n) return 0;
if(rec[cur][W] > 0){
return rec[cur][W];
}
int v1 = dfs(w, v, cur + 1, n, W);
int ans;
//进行剪枝假如不能够拿取的时候把下面的支路都给剪断了,因为有的节点是左节点不拿取之后假如拿取右节点后超出质量的限制
//所以这个时候使用if-else语句来进行比较大小进行返回,不能够拿取的时候直接返回v1
//因为调用右节点的时候说明左节点已经调用完了
if(W >= w[cur]){
int v2 = v[cur] + dfs(w, v, cur + 1, n, W - w[cur]);
ans = max(v1, v2);
}else{
ans = v1;
}
rec[cur][W] = ans;
return ans;
}
}
文章最后发布于: 2018-11-16 13:14:55
相关阅读
职业篇 博客 之前博客系统一直用的 Ghost，然而 Ghost 的新版在vps上升级迁移遇到很多问题，后来索性自己用 nod
很多朋友反应软文写作当中出现了诸多问题。不仅摧残身心，而且软文质量还惨不忍睹。其实，软文写作是一件长期的事情，坚持不下来你是写
确定一个活动的目标，需要结合公司发展、竞争环境、发展策略等因素去思考，有明确的活动目标，才能确定最佳方案。楼盘开工、电影开机都
近期一直在梳理需求收集、需求评审流程，恰好自己带的起点学院就业班邻近毕业答辩，也要模拟需求评审过程，就写一写关于这方面的心得吧
PHP 视频教程下载目录： PHP100 视频教程 1：环境配置与代码调试 PHP100 视频教程 2：PHP 的数据类型与源码调试 PHP100 视频教程 3: