动态规划
动态规划的原理其实也是将大问题划分为小问题,从而一步步获取最优解,但是适用于动态规划求解的问题,子问题往往不是独立的,是具有相互关联性。
背包问题
有一个背包,容量为4磅,现有如下物品:
①要求达到的目标为装入的背包的总价值最大,并且重量不超出
②装入的物品不能重复
思路分析
对于这个题首先最合适的就是列表来分析,找出规律:
物品 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
吉他 | 1500 | 1500 | 1500 | 1500 |
音响 | 1500 | 1500 | 1500 | 3000 |
电脑 | 1500 | 1500 | 2000 | 3500 |
由于是按照吉他-音响-电脑的顺序放入的背包,可以得到明显的两种情况:
①当放的东西小于背包容量时,最优价格即为上一个单元格的装入策略。
②当放的东西大于背包容量时,最优价格即为上一个单元格的装入策略与装入本物品后的最优策略进行比较。
由此产生核心的比较代码:
for (int i = 1; i < v.length ; i++) {
for (int j = 1; j < v[0].length ; j++) {//两次遍历
if(w[i - 1] > j){//第一种情况
v[i][j] = v[i - 1][j];
}else{//第二种情况
if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
//把当前的情况记录到 path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
当思路梳理清楚以后,核心代码就很简单了(体现了动态规划的顺序性与关联性)
全部代码:
public class KnapProblem {
public static void main(String[] args) {
int w[] = {1,4,3};
int[] val = {1500,3000,2000};
int m = 4;
int n = val.length;
//创建二维数组,
//v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值
int[][] v = new int[n+1][m+1];
//为了记录放入商品的情况,我们定一个二维数组
int[][] path = new int[n+1][m+1];
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0;
}
for (int i = 1; i < v.length ; i++) {
for (int j = 1; j < v[0].length ; j++) {
if(w[i - 1] > j){
v[i][j] = v[i - 1][j];
}else{
if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
//把当前的情况记录到 path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
//输出一下 v 看看目前的情况
for(int i =0; i < v.length;i++) {
for(int j = 0; j < v[i].length;j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
//思考如何输出最终结果
int i = path.length - 1;
int j = path[0].length - 1;
while(i > 0 && j > 0){
if(path[i][j] == 1){
System.out.printf("第%d个商品放入到背包\n",i);
j -= w[i-1];
}
i --;
}
}
}
原文地址:http://www.cnblogs.com/robyn2022/p/16912163.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性