-
01背包问题 动态规划
2020-04-13 09:44:2301背包问题 动态规划 01背包问题是一个很经典的动态规划问题了,其特点在于对于当前物品选或不选进行判断 接下来看代码: class Back { static int[] V, M; static int[][] B; public static void main(String[] ...01背包问题 动态规划
01背包问题是一个很经典的动态规划问题了,其特点在于对于当前物品选或不选进行判断
接下来看代码:class Back { static int[] V, M; static int[][] B; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();// 有多少物品 int m = sc.nextInt();// 背包容量是多少 V = new int[n + 1];// 每个物品的重量 M = new int[n + 1];// 每个物品的价值 B = new int[n + 1][m + 1];// 当装了n件商品,且剩余容量为m时的最大价值 for (int i = 1; i <= n; i++) { V[i] = sc.nextInt(); M[i] = sc.nextInt(); } for (int i = 1; i <= n; i++) {// 第i件物品 for (int j = 1; j <= m; j++) {// 当前背包容量 if (V[i] > j) {// 如果该物品比剩余容量大 B[i][j] = B[i - 1][j];// 不拿 } else { // 判断拿还是不拿 int value = Math.max(B[i - 1][j - V[i]] + M[i], B[i - 1][j]); B[i][j] = value; } } } System.out.println(B[n][m]); } }
-
01背包问题动态规划
2019-11-03 20:40:00package algorithm; import java.util....public class _3_10_01背包问题 { static int k; static int C; static int[] v=new int[100]; static int[] w=new int[100]; static int[][] m=new int[100][100...package algorithm; import java.util.Scanner; public class _3_10_01背包问题 { static int k; static int C; static int[] v=new int[100]; static int[] w=new int[100]; static int[][] m=new int[100][100]; static void knapsack(){ for(int i=1;i<=k;i++) m[i][0]=0; for(int i=1;i<=C;i++) m[0][i]=0; for(int i=1;i<=k;i++){ for(int j=1;j<=C;j++){ if(j<w[i]) m[i][j]=m[i-1][j]; else{ m[i][j]=Math.max(m[i-1][j],v[i]+m[i-1][j-w[i]]); } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); knapsack(); } }
-
01 背包问题 动态规划
2020-11-29 19:01:42#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define N 100 int n,c; int w[N],v[N]; int dp[100][1000]; int main(){ memset(dp,0,sizeof(dp));... {#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define N 100 int n,c; int w[N],v[N]; int dp[100][1000]; int main(){ memset(dp,0,sizeof(dp)); cin >> n >>c; int i,j; for(i=1; i<=n; i++) { cin >> w[i] >> v[i]; } for(i=1; i<=n; ++i) { for(j=1; j<=c; ++j) { if(j>=w[i]) dp[i][j] = max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]); else dp[i][j] = dp[i-1][j]; } } cout << dp[n][c]; }
-
01背包问题 动态规划 java实现 简单通俗易懂
2019-06-06 15:05:2801背包问题 动态规划 ** 1.动态规划 什么是动态规划?动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以求出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。 2.01背包...**
01背包问题 动态规划
**
1.动态规划
什么是动态规划?动态规划就是将一个大问题不断向下拆分成小问题,直到拆分出的小问题可以求出其解,然后将小问题的解不断的向上合并,最终得到大问题的解决方案。
2.01背包问题一个旅行者有一个最多能装m公斤的背包,现在有n中物品,每件的重量分别是W1、W2、……、Wn,每件物品的价值分别为C1、C2、……、Cn, 需要将物品放入背包中,要怎么样放才能保证背包中物品的总价值最大?
3.简单思路1.01背包问题与背包问题的区别在于,01背包,物品的选择只有两种一种是拿,另一种是不拿,而背包问题在于,物品可以只取一部分。所以01背包问题不能用贪心算法解决。
2.以dp[i][j]表示用i种物品,重量为j表示所取得的价值。
3.对于第i种物品,如果第i种物品重量大于j,就证明第i种物品肯定不能取,这时的dp[i][j]=dp[i-1][j]
4.如果第i种物品重量小于j,那就会出现两种情况,采用i的话,物品价值dp[i][j]=采用前面的i-1种物品,所占用的重量为j-i.getweight,所产生的价值+第i 种物品的价值。如果不采用i,价值为dp[i-1][j]。换成数学表达式就是dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
5.比如当i=5,j=10时,dp[5][10]就代表了所取得的最大价值。到这里我们就完成了任务的一半,接下为我们要寻找到底哪些物品放入了背包,从前面的表达式我们可以发现,当dp[i][j]=dp[i-1][j-weight]时,这时为i的物品就会放入背包,所以我们从结果,开始往回走,遇到这种情况,就说明有物品放入背包,然后物品数减1,重量减去为i的重量,继续,最后就能求出哪 些物品放入背包了。例题:
1.题目描述:
有如下5种物品,小明的书包最多只能装下8公斤的物品,小明特别贪心,思考怎么选择使自己书包能装下并且得到的价值最大。
物品1:6公斤 价值48元
物品2:1公斤 价值7元
物品3:5公斤 价值40元
物品4:2公斤 价值12元
物品5:1公斤 价值8元2.解题思路:
其实我们正常思维,一般会想,我要尽量装满8公斤,把最大的价值求出来,可是这样的话,就需要用到递归,递归能解出来,只是算法难度高。但是什么是动态规划,动态规划就是逆着来,我要求装8公斤的物品怎么装使得价值最大。我可以先考虑装0公斤,最大价值,再考虑装1公斤最大价值,考虑装2公斤最大价值,装3公斤最大价值,把前面都记录下来。用另外一个temp[i][j]数组记录下来。i呢表示我现在出现的物品的数量,当i循环到最后一个数量的时候就结束了嘛。自己想象一下,我虽然有5件物品,先只给你一件,你判断能不能装下,能装下,那么你就看你装下这件物品,和不装下这件物品哪个价值高,那么记录下来即可。具体填下下面的表试下,真正会填表就差不多了
0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 6 48 0 0 0 0 0 0 48 48 48 1 7 0 7 7 7 7 7 48 55 55 5 40 0 7 7 7 7 40 48 55 55 2 12 0 7 12 19 19 40 48 55 60 1 8 0 8 15 20 27 40 48 56 63
这个表是怎么来的呢?,举个例子,当我横着一排一排填,因为最开始只掉一件物品,开始掉重量是6的物品,到6的时候就能装下了,所以temp[1][6]=48,另外7,8也只有这一件物品填。所以还是一样的。
接下来掉第二个物品,掉下1这个物品了,1的价值是7,也就是temp[2][1] = 7。后面一直到temp[2][5]都是等于7。 重点重点来了,到了temp[2][6]的时候怎么办呢?我们的当然一看就是,我要选第一件物品,它的价值是48,可是选了第一件物品,背包就满了,就不能装第二件重量为1的物品了,所以temp[2][6] = 48。
我们人可以这样思考,关键就来了,关键就是怎么让计算机也可以这样思考呢,我们就需要用代码。其实仔细想想,我掉第二件物品了,判断如果不能装下,那么temp[2][j] = temp[2][j-1] //记住j表示的是我背包现在最大只能装j这么多,那既然这个物品装不下,那么当然不能装了。如果我当前物品重量小于j,那么我就可以选择是装还是不装呢?只要比较装还是不装哪个价值大就行了。如果不装的话价值这个时候的最大价值是不会变的,因为都不装嘛,也就是,temp[2][j] = temp[2-1][j] 。如果我装的话,关键是这个,还是到刚才的到第二件物品的价值为6的时候考虑,如果我装下重量1这个物品,temp[2][6] = temp[2-1][6 - 这个物品的重量] + 物品的价值 //
其实我 temp[2-1][6-这个物品重量]表示我还没装这个物品之前的价值腾出装这个物品的空间,然后加上这个物品的价值进行比较。关键是之前的每一个状态都用数组给记录下来了。关键代码先看一下,结合代码再理解
for(int i=1;i<6;i++) { for(int j=1;j<9;j++) { if(w[i]<=j) { temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]); //其实就是比较物品选还是不选哪种价值大。 }else { temp[i][j] = temp[i-1][j];//第i件物品不能放 } } }
3.代码示例
import java.util.Scanner; public class knapsack { static int[] w = new int[6];//每件物品的重量 static int[] v = new int[6];//每件物品的价值 public static void solution(){ int[][] temp = new int[6][9];//8表示背包最多能放8公斤的重量 for(int j = 0;j < 9;j++){//初始化每一行 temp[0][j] = 0; } for(int i = 1;i < 6;i++){//背包重量为0时,最大价值肯定是0 temp[i][0] = 0; } for(int i = 1;i < 6;i++){//从第一个物品开始选,记录我选了前面出现的物品,背包重量从1-8的能选上的最大值 for(int j = 1;j < 9;j++){//当i循环到最后一层5的时候,也就是得到了,我5件物品都选上的时候的最大值 if(w[i] <= j){//重量比这个状态小,那么就能放。就是放与不放的问题,观察室放重量大还是不放重量大 temp[i][j] = Math.max(temp[i-1][j], temp[i-1][j-w[i]]+v[i]); }else{ temp[i][j] = temp[i-1][j];//第i件物品不能放 } } } for(int i = 0;i < 6;i++){ for(int j = 0;j < 9;j++){ System.out.print(temp[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { System.out.println("请依次输入重量和价值:"); Scanner scn = new Scanner(System.in); for (int i = 0; i < 6; i++) { w[i] = scn.nextInt();//输入重量 v[i] = scn.nextInt();//输入价值 } solution(); } }
-
国王的金矿:01背包问题 动态规划解法
2020-01-21 16:49:05国王的金矿:01背包问题 动态规划解法 题目描述 有一个国家发现了 n 座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。 参与挖矿工人的总数是 m 人。 每座金矿要么全挖, 要么不挖,不能派出一半人挖取... -
c c++ 01背包问题动态规划解决
2013-11-05 16:45:5401背包问题解决方法不少,动态规划是其中之一,动态规划的问题解题思路都差不多(一些浅见),基本要素是最优子结构性质,子问题重叠性质,自底向上的求解方法。只要了解了基本要素,那么这种题型也会更好理解。本题... -
01背包问题java_01背包问题 动态规划 java实现
2021-02-12 15:31:15日常吐槽,日常打代码,理论可以去看其他博客,只贴出代码,代码有注释public ...//自底向上,若最后一个物体的重量小于背包的总容量,取最后一个物体的重量为界限//小于w[n]都放不不了for(int j=0;j<=jMax;j++... -
01背包问题动态规划法求解
2012-07-27 09:04:2901背包问题动态规划法求解 一问题描述: 有N件商品,每种商品都有各自的重量和价值,有一个背包,总容量是V。现在从这N种商品中挑选若干件放入背包中,要求每种商品最多放入一次,要使放入背包中商品总价值... -
【转】01背包问题动态规划详解
2012-08-11 18:37:00【转】01背包问题动态规划详解 转载自sunstar1989 最终编辑中华复生母 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。比如01背包问题。 ... -
白书2.3.1 01背包问题动态规划
2019-11-25 22:14:06有n个重量和价值分别为wi, ...这是01的背包的问题最终形态,从递归思考过来的话应该不难理解 #include <bits/stdc++.h> using namespace std; int n, W; int w[100], v[100], dp[100][10000]; int main() { ... -
01背包问题动态规划-atao
2018-04-05 14:17:5701背包类似问题一般是给3个参数 1:sum 背包总重量 2:w[]数组, 数组每个数为单个物品重量 3:v[]数组,每个数为单个物品价值, 一般就是要求在背包能装得下的情况下,保证价值最大。 核心思路: 就是1个物品和... -
01背包问题动态规划算法
2018-03-20 17:09:42#include <cstdio> #define max(u,v) (u)>(v)?(u):(v) #define min(u,v) (u)>(v)?(v):(u) int m[10][20];...void Knapsack(int v[10], int w[10], int c, int n, int m... -
01背包问题 动态规划 c语言实现
2017-09-06 16:15:47* 基本的0-1背包问题: * 已知有N类物品,每类物品都只有一件,对应的重量为w[i],价值为v[i]。 * 背包最多承重为W,在不超出承重范围的前提下,求能拿的物件的最大价值为多少 * *这是DP的一个经 -
01背包问题动态规划详解
2011-11-23 14:30:01比如01背包问题。 /* 一个旅行者有一个最多能用M公斤的背包,现在有N件物品, 它们的重量分别是W1,W2,...,Wn, 它们的价值分别为P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。 输入格式: M,N... -
01背包问题 动态规划 c swift 双版本
2017-12-14 03:35:09概念:为什么这种题目会 用动态规划,不用贪心算法? --我个人理解是,贪心算法每一步的最优解,可能导致最后的答案不是最优解。 --而动态规划,可以在上一步或前几步不是最优解的情况下,解得当前这一步是最优解。 ...
-
python文件运行报错(文件编码)
-
凡客诚品 微博营销实践暨品牌创新.ppt
-
C++代码规范和Doxygen根据注释自动生成手册
-
latex write pseudocode
-
记一次“no module named arcpy”的解决心路历程
-
联想EXCEL培训资料.ppt
-
(js)leetcode 1295. 统计位数为偶数的数字
-
龙芯生态应用开发基础:C语言精要
-
朱老师c++课程第3部分-3.5STL的其他容器讲解
-
qBittorrentEE_v4.3.1.11_便携版.zip
-
基于电商业务的全链路数据中台落地方案(全渠道、全环节、全流程)
-
佳能打印机G2800不需要软件的清零方法.txt
-
华为机试题之字符串最后一个单词的长度
-
基于Qt的LibVLC开发教程
-
验证码案例
-
在 Linux 上构建企业级 DNS 域名解析服务
-
【Python-随到随学】 FLask第一周
-
NFS 网络文件系统
-
OC.Gen-X.2.9.2.dmg
-
LVS + Keepalived 实现 MySQL 负载均衡与高可用