java背包问题
① java回溯和递归的区别，主要什么回溯怎么用，有代码最好
N皇后问题的非递归迭代回溯法java代码实现
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class NQueen {
static int n; // 皇后个数
static int[] x; // 当前解如{0，2，4，1，3}分别代表第1、2、3、4列的行值
static int totle; // 可行方案个数
public static void main(String[] args) {
int input = 0; //输入n值
int sum = 0; //可行方案个数
String temp; //临时存储输入值
System.out.println("请输入N后问题的N值：");
try {
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
temp = br.readLine();
input = Integer.parseInt(temp); //将输入值转换为int保存
if(input<=0){
throw new IOException("别输负数好不？");
}
System.out.println("输入的数是：" + input);
sum = nQueen(input); //调用nqueen方法
System.out.println("可行方案个数为：" + sum); //输出sum
} catch (IOException e) {
System.out.println(e.getMessage());
}catch (NumberFormatException e){
System.out.println("请输入数字。。。");
}
}
private static int nQueen(int input) {
n = input; //把输入给全局变量n
totle = 0; //初始化totle
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0; //初始化x
backtrack(); //调用回溯算法
return totle;
}
private static void backtrack() {
int k = 1;
while (k > 0) {
x[k] += 1; //第k列皇后向下移一行
while ((x[k] <= n) && !(place(k))){ //如果当前第k列皇后未出界或者和其他皇后冲突
x[k] += 1; //第k列皇后向下移一行继续寻找
System.out.println("在第"+k+"行 "+"第"+x[k]+"列放置皇后");
System.out.print("当前方案为 ");
for(int i=1;i<=k;i++) //打印寻找策略
System.out.print(x[i]+" ");
System.out.println();
}
if (x[k] <= n) //找到一个值并且未出界
if (k == n) { //已是最后一列说明已找到一个方案
totle++;
System.out.print("可行方案为： ");
for (int i = 1; i <= n; i++)
System.out.print(x[i] + " ");
System.out.println();
} else { //不是最后一列故寻找下一列
k++;
x[k] = 0;
}
else //找到的值已经出界，回退到上一列
k--;
}
}
//判断皇后是否冲突
private static boolean place(int k) {
for (int j = 1; j < k; j++)
if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
return false;
return true;
}
}
② java 问题，是面试题，谁能答出来，我觉得是高手了！不是智力题的，要用算法去实现！
先将石头按质量从大到小放到数组stone[0]~stone[99]中。然后对A、B两个组按贪心法进行选择：
1、让A先取；
2、循环进行剩下的99次选取，每次选取时，总重量小的具有选取权。
具体过程描述可如下：
//前提条件：数组stone中从大到小存放了100个数。
list listA, listB;
list *p;
listA.Insert(stone[0]);
for(int i = 1; i < 100; i++) {
p = listA.Sum( ) < listB.Sum( ) ? &listA : &listB;
*p.Insert(stone[i]);
}
③ 背包问题算法java实现
任何语言都是一样的，贪心算法，先按价值除重量排序，一个一个的加到背包里，当超过背包允许的重量后，去掉最后加进去一个，跳过这一个以后再加后面的，如果还是超重，再跳过这个，一直到价值最大化位置。
④ 求Java高手解答】问题提交不上，请看链接 http://blog.csdn.net/eabcde/article/details/8184925
（昨天晚上给的代码后来发现了个Bug，现在已经重新更正了代码）
补充一下：如果原题第一题的答案是3900的话，根据这个推测到，题目的意思需要更加明确一下：购买的物品是不重复的。
这是一个算法问题，分类是：背包问题。我用的是回溯法，遍历每一种可能的情况，求出最大值。算法代码如下：包含了main方法测试，输入的测试数据为
int[][] arr = { { 1000, 5 }, { 800, 2 }, { 400, 5 }, { 300, 5 },{ 400, 3 }, { 200, 2 } };
程序输出结果为：
最大乘积和为 : 3900
最大的组合情况为: [ 400 , 5 ] [ 300 , 5 ] [ 200 , 2 ]
arr数组应该是从文件里面读取的，我设计的是主要的算法，用arr数组输入，你从文件里面读取数据，按照规则复制给 arr数组就行。
代码经过初步测试：
import java.util.ArrayList;
import java.util.List;
public class Bai {
private int[][] res;
private int max = 0;
private List<ArrayList<Integer>> resList;
public int getResult(int[][] arr) {
res = new int[arr.length - 1][2];
// 算法思想：先要对商品等级与价格，按照价格非增序地排序
sort(arr);
// 然后用回溯法，递归地遍历每一种情况，比较出最大值
getRes(arr, arr[0][0], 1, 0);
return max;
}
// 先降序排序
private void sort(int[][] arr) {
for (int i = 1; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i][0] < arr[j][0]) {
int[][] tem = new int[1][2];
tem[0][0] = arr[i][0];
tem[0][1] = arr[i][1];
arr[i][0] = arr[j][0];
arr[i][1] = arr[j][1];
arr[j][0] = tem[0][0];
arr[j][1] = tem[0][1];
}
}
}
}
// 采用回溯法，递归地遍历每一种情况，求出最佳结果
private void getRes(final int[][] arr, int left, int begin, int cen) {
if ((left < arr[arr.length - 1][0]) || begin >= arr.length) {
List<ArrayList<Integer>> theResList = new ArrayList<ArrayList<Integer>>();
int sum = 0;
for (int i = 0; i < cen; i++) {
sum += res[i][0] * res[i][1];
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(res[i][0]);
list.add(res[i][1]);
theResList.add(list);
}
if (sum > max) {
max = sum;
resList = theResList;
}
return;
}
for (int i = begin; i < arr.length; i++) {
if (arr[i][0] <= left) {
res[cen][0] = arr[i][0];
res[cen][1] = arr[i][1];
getRes(arr, left - arr[i][0], i + 1, cen + 1);
}
}
}
public List<ArrayList<Integer>> getResList() {
return resList;
}
public static void main(String[] args) {
int[][] arr = { { 1000, 5 }, { 800, 2 }, { 400, 5 }, { 300, 5 },
{ 400, 3 }, { 200, 2 } };
Bai = new Bai();
int max = .getResult(arr);
System.out.println("最大价值为 : " + max);
List<ArrayList<Integer>> res = .getResList();
System.out.print("最大的组合情况为: ");
for (ArrayList<Integer> arrayList : res) {
System.out.print("[ " + arrayList.get(0) + " , " + arrayList.get(1)
+ " ] ");
}
}
}
⑤ 回溯法解决0-1背包问题 java写的 求大神指点~~~~(>_<)~~~~
因为你把n和c 定义为static ,而且初始化为0,。数组也为静态的,一个类中静态的变量在这个类加载的时候就会执行，所以当你这类加载的时候，你的数组static int[] v = new int[n];
static int[] w = new int[n];
就已经初始化完毕，而且数组大小为0。在main方法里动态改变n的值是改变不了已经初始化完毕的数组的大小的，因为组已经加载完毕。
我建议你可以在定义n,c是就为其赋初值。比如（static int n=2 static int c=3）
⑥ java写背包问题没看懂
m[][] 就是一个二维数组。
你平时看见的a[] 这样的数组是用来定义一维数组的，里面放的东西你应该明白。二维数组其实和一维数组差不多，只不过二维数组的m[]放的是另外一个m1[]这样的数组。两个数组就从线变成了面，类似于XY坐标图了。这就是二维数组，面上的关系。
⑦ java小练习
package cn.com.zhl;
import java.util.Date;
/*评估工具类
评测标准:背包中物品质量总和要小于等于maxWeight;背包中物品的总价格要尽量最大化*/
public class Drivers {
/*评测参数初始化,不同的评测可以通过多次修改初始化参数来完成，也可以把参数写成随机赋值的初始化方式*/
int number = 10;//物件总数量
int maxWeight =50;//背包最大承重量
int[] w = new int[10];//已知的10个物件的重量
int[] b = new int[10];//已知的10个物件的单价
/*评估参数*/
int totalWeight; //执行后背包实际重量
int totalBenefit;//执行后背包中物件的总价值
//评估方法solverA的执行效率和精确度
public void getResultA(){
long start = new Date().getTime();//获得程序执行前的时间
boolean take[] = new Knapsack().solverA(number, maxWeight, w, b);//执行A方案并返回布尔数组
long end = new Date().getTime();//获得程序执行后的时间
System.out.println("solverA方法的执行时间是："+(end - start));//
for(int i = 0; i <take.length; i++){
totalWeight = 0;
totalBenefit = 0;
if(take[i]==true){
totalWeight = totalWeight + w[i];
totalBenefit = totalBenefit + b[i];
}
//输出评估结果
if(totalWeight>maxWeight){
System.out.println("【失败的结果】，计算出的总重量超过了背包可以容纳的总重量");
}else{
System.out.println("【总重量】=" + totalWeight);//获得solverA得到的总质量
System.out.println("【总价格】=" + totalBenefit);//获得solverA得到的总价格
}
}
}
//评估方法solverB的执行效率和精确度
public void getResultB(){
long start = new Date().getTime();//获得程序执行前的时间
boolean take[] = new Knapsack().solverB(number, maxWeight, w, b);//执行B方案并返回布尔数组
long end = new Date().getTime();//获得程序执行后的时间
System.out.println("solverB方法的执行时间是："+(end - start));//
for(int i = 0; i <take.length; i++){
totalWeight = 0;
totalBenefit = 0;
if(take[i]==true){
totalWeight = totalWeight + w[i];
totalBenefit = totalBenefit + b[i];
}
//输出评估结果
if(totalWeight>maxWeight){
System.out.println("【失败的结果】，计算出的总重量超过了背包可以容纳的总重量");
}else{
System.out.println("【总重量】=" + totalWeight);//获得solverA得到的总质量
System.out.println("【总价格】=" + totalBenefit);//获得solverA得到的总价格
}
}
}
public static void main(String[] args){
new Drivers().getResultA();
System.out.println("------------------------------------------------------");
new Drivers().getResultB();
//根据输出的结果判断A和B的执行效率以及精确程度，可以通过多次更换初始化数据来进行多次评估以得出综合结论
}
}
⑧ 01背包问题变种：从给定的N个正数中选取若干个数之和最接近M的JAVA写法
BIAS0:= (C-MA(C,2))/MA(C,2)*100;
BIAS1 := (C-MA(C,12))/MA(C,12)*100;
BIAS2 := (C-MA(C,26))/MA(C,26)*100;
BIAS3 := (C-MA(C,48))/MA(C,48)*100;
HXL:=V/CAPITAL*100;
D1:=INDEXC;
D2:=MA(D1,56);
DR2:=D1/D2<0.94;
E1:=(C-HHV(C,12))/HHV(C,12)*10;
E2:=(C-REF(C,26))/REF(C,26)*10;
⑨ 关于这个java语言描述的0-1背包问题是否有错误
有点问题：
public static void knapsack(int[]v,int[]w,int c,int[][]m)
{
int n=v.length-1;
int jMax=Math.min(w[n]-1,c);
for(int j=0;j<=jMax;j++)
m[n][j]=0;
for(int j=w[n];j<=c;j++)
m[n][j]=v[n];
for(int i=n-1;i>1;i--)
{
jMax=Math.min(w[i]-1,c);
for(int j=0;j<=jMax;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)
m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);
}
public static void traceback(int[][]m,int[]w,int c,int[]x)
{
int n=w.length-1;
for(int i=1;i<n;i++) {
if(m[i][c]==m[i+1][c])x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>0)?1:0;
}
//int n=w.length-1;
for(int i=1;i<n;i++)
if(m[i][c]==m[i+1][c])x[i]=0;
else {
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c]>0)?1:0;
}
⑩ 0-1背包问题java代码
importjava.io.BufferedInputStream;
importjava.util.Scanner;
publicclasstest{
publicstaticint[]weight=newint[101];
publicstaticint[]value=newint[101];
publicstaticvoidmain(String[]args){
Scannercin=newScanner(newBufferedInputStream(System.in));
intn=cin.nextInt();
intW=cin.nextInt();
for(inti=0;i<n;++i){
weight[i]=cin.nextInt();
value[i]=cin.nextInt();
}
cin.close();
System.out.println(solve(0,W,n));//普通递归
System.out.println("=========");
System.out.println(solve2(weight,value,W));//动态规划表
}
publicstaticintsolve(inti,intW,intn){
intres;
if(i==n){
res=0;
}elseif(W<weight[i]){
res=solve(i+1,W,n);
}else{
res=Math.max(solve(i+1,W,n),solve(i+1,W-weight[i],n)+value[i]);
}
returnres;
}
publicstaticintsolve2(int[]weight,int[]value,intW){
int[][]dp=newint[weight.length+1][W+1];
for(inti=weight.length-1;i>=0;--i){
for(intj=W;j>=0;--j){
dp[i][j]=dp[i+1][j];//从右下往左上，i+1就是刚刚记忆过的背包装到i+1重量时的最大价值
if(j+weight[i]<=W){//dp[i][j]就是背包已经装了j的重量时，能够获得的最大价值
dp[i][j]=Math.max(dp[i][j],value[i]+dp[i+1][j+weight[i]]);
//当背包重量为j时，要么沿用刚刚装的，本次不装，最大价值dp[i][j]，要么就把这个重物装了，那么此时背包装的重量为j+weight[i]，
//用本次的价值value[i]加上背包已经装了j+weight[i]时还能获得的最大价值，因为是从底下往上，刚刚上一步算过，可以直接用dp[i+1][j+weight[i]]。
//然后选取本次不装weight[i]重物时获得的最大价值以及本次装weight[i]重物获得的最大价值两者之间的最大值
}
}
}
returndp[0][0];
}
}