转自http://zyfromcq.iteye.com/blog/1233471
0/1背包问题的动态规划法求解，前人之述备矣，这里所做的工作，不过是自己根据理解实现了一遍，主要目的还是锻炼思维和编程能力，同时，也是为了增进对动态规划法机制的理解和掌握。
值得提及的一个问题是，在用 JAVA 实现时， 是按算法模型建模，还是用对象模型建模呢？ 如果用算法模型，那么 背包的值、重量就直接存入二个数组里；如果用对象模型，则要对背包以及背包问题进行对象建模。思来想去，还是采用了对象模型，尽管心里感觉算法模型似乎更好一些。有时确实就是这样，对象模型虽然现在很主流，但也不是万能的，采用其它的模型和视角，或许可以得到更好的解法。
背包建模：
动态规划法总结：
1. 动态规划法用于求解非最优化问题：
当问题实例P(n)的解由子问题实例的解构成时，比如 P(n) = P(n-1) + P(n-2) [斐波那契数列] ，而 P(n-1) 和 P(n-2)可能包含重合的子问题，可以使用动态规划法，通过自底向上的迭代，求解较小子问题实例的解，并作为求解较大子问题实例的解的基础。关键思想 是： 避免对子问题重复求解。
比如： 求斐波那契数 F(5)：
F(5) = F(4) + F(3);
子问题： F(4) = F(3) + F(2) ;
F(3) = F(2) + F(1);
F(2) = F(1) + F(0)
F(2) = F(1) + F(0);
子问题： F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
由上面的计算过程可知，如果单纯使用递归式，则子问题 F(2) 被重复计算了2次；当问题实例较大时，这些重复的子问题求解就会耗费大量不必要的时间。 若使用动态规划法，将 F(2) 的值存储起来，当后续计算需要的时候，直接取出来， 就可以节省不少时间。
另一个比较典型的例子是： 求解二项式系数 C(n, k) = C(n-1, k) + C(n-1, k-1)
2. 动态规划法求解最优化问题：
当问题实例P(n) 的最优解 可以从 问题实例 P(n-1) 的最优解 构造出来时，可以采用动态规划法，一步步地构造最优解。
关键是掌握动态规划法求解问题时的分析方法，如何从问题导出 解的递推式。 实际上，当导出背包问题的递归式后，后来的工作就简单多了，如何分析背包问题，导出其最优解的递推式，我觉得，这才是最关键的地方！问题分析很重要！
如下代码有修改
package org.corpus.util;
import java.util.ArrayList;
import java.util.List;
import org.corpus.util.KnapsackProblem.Knapsack;
/**
* 求解背包问题：
* 给定 n 个背包，其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn
* 要放入总承重为 totalWeight 的箱子中，
* 求可放入箱子的背包价值总和的最大值。
*
* NOTE: 使用动态规划法求解 背包问题
* 设 前 n 个背包，总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n];
* 求解最优值：
* 1. 若 j < wn, 则 ： v[n,j] = v[n-1,j];
* 2. 若 j >= wn, 则：v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。
*
* 求解最优背包组成：
* 1. 若 v[n,j] > v[n-1,j] 则 背包 n 被选择放入 b[n],
* 2. 接着求解前 n-1 个背包放入 j-wn 的总承重中，
* 于是应当判断 v[n-1, j-wn] VS v[n-2,j-wn], 决定 背包 n-1 是否被选择。
* 3. 依次逆推，直至总承重为零。
*
* 重点： 掌握使用动态规划法求解问题的分析方法和实现思想。
* 分析方法： 问题实例 P(n) 的最优解S(n) 蕴含 问题实例 P(n-1) 的最优解S(n-1);
* 在S(n-1)的基础上构造 S(n)
* 实现思想： 自底向上的迭代求解 和 基于记忆功能的自顶向下递归
*/
public class KnapsackProblem<T extends Knapsack> {
public static class Knapsack{
public int weight;
public int value;
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
/** 指定背包 */
private T[] bags;
/** 总承重 */
private int totalWeight;
/** 给定背包数量 */
private int n;
/** 前 n 个背包，总承重为 totalWeight 的最优值矩阵 */
private int[][] bestValues;
/** 前 n 个背包，总承重为 totalWeight 的最优值 */
private int bestValue;
/** 前 n 个背包，总承重为 totalWeight 的最优解的物品组成 */
private List<T> bestSolution;
public KnapsackProblem(T[] bags, int totalWeight) {
this.bags = bags;
this.totalWeight = totalWeight;
this.n = bags.length;
if (bestValues == null) {
bestValues = new int[n+1][totalWeight+1];
}
}
/**
* 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题
*
*/
public void solve() {
// System.out.println("给定背包数量："+bags.length);
// for(Knapsack b: bags) {
// System.out.println(b);
// }
// System.out.println("给定总承重: " + totalWeight);
// 求解最优值
for (int j = 0; j <= totalWeight; j++) {
for (int i = 0; i <= n; i++) {
if (i == 0 || j == 0) {
bestValues[i][j] = 0;
}
else
{
// 如果第 i 个背包重量大于总承重，则最优解存在于前 i-1 个背包中，
// 注意：第 i 个背包是 bags[i-1]
if (j < bags[i-1].getWeight()) {
bestValues[i][j] = bestValues[i-1][j];
}
else
{
// 如果第 i 个背包不大于总承重，则最优解要么是包含第 i 个背包的最优解，
// 要么是不包含第 i 个背包的最优解， 取两者最大值，这里采用了分类讨论法
// 第 i 个背包的重量 iweight 和价值 ivalue
int iweight = bags[i-1].getWeight();
int ivalue = bags[i-1].getValue();
bestValues[i][j] =
Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);
} // else
} //else
} //for
} //for
// 求解背包组成
if (bestSolution == null) {
bestSolution = new ArrayList();
}
int tempWeight = totalWeight;
for (int i=n; i >= 1; i--) {
if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {
bestSolution.add(bags[i-1]); // bags[i-1] 表示第 i 个背包
tempWeight -= bags[i-1].getWeight();
}
if (tempWeight == 0) { break; }
}
bestValue = bestValues[n][totalWeight];
}
/**
* 获得前 n 个背包， 总承重为 totalWeight 的背包问题的最优解值
* 调用条件： 必须先调用 solve 方法
*
*/
public int getBestValue() {
return bestValue;
}
/**
* 获得前 n 个背包， 总承重为 totalWeight 的背包问题的最优解值矩阵
* 调用条件： 必须先调用 solve 方法
*
*/
public int[][] getBestValues() {
return bestValues;
}
/**
* 获得前 n 个背包， 总承重为 totalWeight 的背包问题的最优解值矩阵
* 调用条件： 必须先调用 solve 方法
*
*/
public List<T> getBestSolution() {
return bestSolution;
}
}
测试代码：
public class KnapsackTxt {
public static void beibao(String dir, Txt[] source, double double1) {
int target=Math.round((float)double1);
KnapsackProblem<Txt> kp = new KnapsackProblem<Txt>(source, target);
kp.solve();
int num0=0;
for (Txt txt: kp.getBestSolution()) {
Txt txtn=(Txt)txt;
String fn=txtn.f.getAbsolutePath();
fn=fn.replaceAll("business2", "business_small");
try {
FileCopy.copy(txtn.f.getAbsolutePath(), fn);
// String utf16= UFileReader.read(out[i].f, "UTF-16");
// WriteFileUtils.writeFile( fn,utf16);
} catch (Exception e) {
System.out.println(txtn.f+">>>");
e.printStackTrace();
}
num0=num0+txtn.value;
}
if(target>num0){
System.out.println("* "+dir+"\t目标值 "+target+ "\t"+" 实际值"+num0 );
}else{
System.out.println(" "+dir+"\t目标值 "+target+ "\t"+" 实际值"+num0);
}
}
}
import java.io.File;
import org.corpus.util.KnapsackProblem;
public class Txt extends KnapsackProblem.Knapsack{
public int len;
public String dir;
public String name;
public File f;
public int level;
public String ppath(){
return f.getParentFile().getParentFile().getAbsolutePath();
}
}
原文测试代码，内容比较符合背包：
package com.wootion.algorithmic;
public class KnapsackTest {
public static void main(String[] args) {
Knapsack[] bags = new Knapsack[] {
new Knapsack(2,13), new Knapsack(1,10),
new Knapsack(3,24), new Knapsack(2,15),
new Knapsack(4,28), new Knapsack(5,33),
new Knapsack(3,20), new Knapsack(1, 8)
};
int totalWeight = 10;
KnapsackProblem kp = new KnapsackProblem(bags, totalWeight);
kp.solve();
System.out.println(" -------- 该背包问题实例的解: --------- ");
System.out.println("最优值：" + kp.getBestValue());
System.out.println("最优解【选取的背包】: ");
System.out.println(kp.getBestSolution());
System.out.println("最优决策矩阵表：");
int[][] bestValues = kp.getBestValues();
for (int i=0; i < bestValues.length; i++) {
for (int j=0; j < bestValues[i].length; j++) {
System.out.printf("%-5d", bestValues[i][j]);
}
System.out.println();
}
}
}
分享到：
相关推荐
【标题】"pack.rar_背包_背包算法_背包算法 MATLAB_背包算法MATLAB" 提供了一个关于使用MATLAB实现背包问题算法的详细资料。背包问题是一个经典的优化问题，广泛应用于资源分配、决策制定等领域。在这里，我们将深入...
背包算法 背包算法JAVA实现 背包算法JAVA实现
原先在网上找到某位大虾写的一个简单的背包算法，于是在其基础上改成适合我们目前项目中要求的背包算法。此算法要求传入一组对象集合（其中的对象中只包含主键和值）和某个条件值，然后能打印sum（对象.值)条件的1个...
**背包算法详解** 在计算机科学和算法设计中，背包问题是一种经典的优化问题，它源于组合优化和图论领域。背包问题通常与资源分配、决策分析和最优化策略相关，广泛应用于项目管理、库存控制、软件工程等多个领域。...
在这个0-1背包问题的解决方案中，遗传算法被用来寻找能够最大化总价值的物品组合。 在MATLAB环境中实现遗传算法解决0-1背包问题，主要涉及以下步骤： 1. 初始化种群：随机生成一定数量的个体（解），每个个体代表...
基于0-1背包算法的社交网络行为隐写术 本文提出了一种基于0-1背包算法的社交网络行为隐写术，以解决传统隐写术的安全性问题。该方法通过引入0-1背包人员分配协议，降低了发送者和接收者有较多的共同好友这一限制...
《基于MATLAB的遗传算法在背包问题中的应用》 背包问题是一种典型的组合优化问题，广泛存在于资源分配、项目选择等领域。在本项目中，我们利用MATLAB强大的计算能力，结合遗传算法，对背包问题进行了有效的求解，以...
在NOIP这样的信息学竞赛中，背包问题是检验参赛者逻辑思维、编程能力和算法理解的重要题目类型。选手需要在限定时间内设计并实现高效的解决方案。理解和掌握背包问题的解法，对于提升信息技术素养，培养计算思维有着...
Java背包算法规划求解是一种经典的优化问题，常用于解决资源有限条件下的最大化效益问题。在给定的场景中，我们有n种商品，每种商品只有一个，并且有200块钱去购物，目标是使购买的商品总价值最大。这个问题可以抽象...
这个标题暗示我们这里有一个名为“baglock”的程序，它可能是用于实现某种特定类型的背包问题的加密或解密算法。"pridebt1"可能是该算法的特定版本或者开发者的一个标识。 【描述】：“用C实现的关于密码学编程的...
0-1背包问题和部分背包问题是运筹学和计算机科学中的经典优化问题，它们在资源分配、任务调度、投资决策等多个领域有广泛应用。本实验主要关注这两种问题的算法实现，特别是动态规划和贪心策略。 0-1背包问题源于一...
C++编写的背包算法程序 cpp 动态规划
01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码 01背包问题算法 动态规划 代码
用 PHP 实现的 01 背包算法，参考了网上的相关 C++ 算法，用来方便 PHP 程序员改造使用，我是用它来实现在指定宽度的栏中整齐的排列一堆标签云，效果非凡且神奇，初次使用时一瞬间的确有这样的感觉。
标题中的“beibao.rar”是一个压缩包文件，其中包含了关于“背包问题”的解决方法，主要使用了“贪婪算法”并以MATLAB编程语言进行实现。贪婪算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的...
输入物品数量n,报的容量m,每个物品的体积,每个物品的价值 输入：最大价值
它描述的是这样的场景：我们有一组物品，每种物品都有一个重量和价值，我们需要选择一部分物品放入一个容量有限的背包中，使得放入背包的物品总重量不超过背包的容量，同时使这些物品的总价值最大。0-1背包问题的...
0-1背包问题在实际应用中有很多变种，如完全背包问题（每个物品可以无限数量放入背包）、多重背包问题（每个物品有固定数量）等，每种变种都有相应的优化算法。理解和掌握0-1背包问题及其算法，对于解决实际生活中...
### 贪心算法在背包问题中的应用及C语言实现 #### 一、贪心算法简介 贪心算法是一种在每个步骤中都选择局部最优解的策略，希望通过一系列的局部最优选择来达到全局最优解的目的。它适用于某些特定的问题类型，在...
C++实现回溯算法 0 1 背包算法 本文将详细介绍 C++ 实现回溯算法 0 1 背包算法的知识点。 首先，需要了解背包问题的定义。背包问题是指在有限容量的背包中，如何选择物品以达到最大价值的优化问题。在这里，我们...