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];
}
}