背包问题描述
代码以及详细描述:
package cn.edu.xmu.acm.dp;
/**
* 求解背包问题:
* 给定 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)
* 实现思想: 自底向上的迭代求解 和 基于记忆功能的自顶向下递归
*/
import java.util.ArrayList;
public class KnapsackDP {
/** 指定背包 */
private Knapsack[] bags;
/** 总承重 */
private int totalWeight;
/** 给定背包数量 */
private int n;
/** 前 n 个背包,总承重为 totalWeight 的最优值矩阵 */
private int[][] bestValues;
/** 前 n 个背包,总承重为 totalWeight 的最优值 */
private int bestValue;
/** 前 n 个背包,总承重为 totalWeight 的最优解的物品组成 */
private ArrayList<Knapsack> bestSolution;
public KnapsackDP(Knapsack[] 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("给定背包:");
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<Knapsack>();
}
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 ArrayList<Knapsack> getBestSolution() {
return bestSolution;
}
}
package cn.edu.xmu.acm.dp;
public class TestKnapsackDP {
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 = 12;
KnapsackDP kp = new KnapsackDP(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();
}
}
}
package cn.edu.xmu.acm.dp;
public class Knapsack {
/** 背包重量 */
private int weight;
/** 背包物品价值 */
private int value;
/***
* 构造器
*/
public Knapsack(int weight, int value) {
this.value = value;
this.weight = weight;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
public String toString() {
return "[weight: " + weight + " " + "value: " + value + "]";
}
}
参考:0/1背包问题的动态规划法求解 —— Java 实现
分享到:
相关推荐
动态规划的背包问题,是不是一度让你很苦恼?不急,有了这个PPT,能让你做背包问题易如反掌。
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1...动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。
计算机算法设计与分析动态规划法求解0-1背包问题的改进算法完整解释
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
01背包问题动态规划,动态规划求解找零问题和背包问题C++代码
用c语言实现的基于动态规划求解01背包问题,,其中2.txt中的内容为: 4 5 2 1 3 2 12 10 20 15
算法设计实验报告,包括:贪心法求解背包问题的基本思想、动态规划法求解0/1背包问题的基本思想及各自的时间复杂度分析,两种问题的区别,C++实现代码,运行截图,实验心得。
算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考
C++语言描述,VC++6。0下运行,用动态规划法求解0/1背包问题,代码里现有很详细的注释,是学习算法的很好参考。
使用动态规划求解01背包问题的程序,使用C语言编写。
用混合遗传算法求解背包问题 将贪婪修复方法与遗传算法相结合,构成混和遗传算法,并求解经典背包问题。
算法设计实验报告,包括:蛮力、动态规划、回溯、分支限界四种算法求解0/1背包问题的基本思想、时间复杂度分析,C++实现代码,运行结果截图,实验心得。
【背包问题】基于遗传算法求解多背包问题matlab源码
用动态规划的思想解决背包问题。过程中减少了不必要的重复计算。
应用:1:该问题可以通过“局部寻优”逐步过渡到“整体最优”,这是贪心选择性质与“动态规划”的主要差别。2:最优子结构性质:某个问题的整体最优解包含了“子”问题的最优解。完整的代码如下: 代码如下:#include...
基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
Python背包问题动态规划求解(一维和二维数组).zip
1) 动态规划法求解问题的一般思路,动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。 2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现...
实验目标实验目标: ...(1)掌握用动态规划方法求解实际问题的基本思路。 (2)进一步理解动态规划方法的实质,巩固设计动态规划算法的基本步骤。 实验任务: (1) 实现0-1背包问题的动态规划算法