求java大神帮忙

背包问题的求解[问题描述]假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…,wn的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1+w2+…+wn=T... 背包问题的求解[问题描述]假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1 +w2 + … + wn=T,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:(1,4,3,2)(1,4,5)(8,2)(3,5,2)。[实现提示]可利用回溯法的设计思想来解决背包问题。首先将物品排成一列,然后顺序选取物品装入背包,假设已选取了前i 件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品"太大"不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明"刚刚"装入背包的那件物品“不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。由于回溯求解的规则是"后进先出"因此自然要用到栈。 展开
 我来答
百度网友9fcbcc4
2014-01-13
知道答主
回答量:49
采纳率:0%
帮助的人:12.2万
展开全部
/**
* 求解背包问题:
* 给定 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)
* 实现思想: 自底向上的迭代求解 和 基于记忆功能的自顶向下递归
*/
package algorithm.dynamicplan;
import java.util.ArrayList;
public class KnapsackProblem {

/** 指定背包 */
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 KnapsackProblem(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;
}

}
更多追问追答
追问
不要价值了啦 有重量就好了
追答
那就自己把涉及价值的代码删除吧
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
chong咏
2014-01-13 · 超过19用户采纳过TA的回答
知道答主
回答量:65
采纳率:0%
帮助的人:47.6万
展开全部
0-1背包问题!!很复杂的问题,可惜当初没有很认真的听课,楼主加油啊
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
维特bP
2014-01-13 · TA获得超过406个赞
知道小有建树答主
回答量:659
采纳率:33%
帮助的人:180万
展开全部
看算法设计的书吧,背包算法是经典算法。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 更多回答(1)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式