完全背包問題

一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，...,Wn,每件的價值分別為C1,C2,...,Cn.若的每種物品的件數(shù)足夠多.求旅行者能獲得的最大總價值。

貪心法:貪心法又叫貪婪算法，是指，對問題求解時，總是找出當(dāng)前局部最優(yōu)解。也就是說，不從整體最優(yōu)考慮，

它所找出的某種意義上的局部的最優(yōu)解。貪心算法并不是對所有問題一定能找出整體的最優(yōu)解。但對范圍相當(dāng)廣泛

的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

輸入示例:

17

3 4 7 8 9

4 5 10 11 13

其得出的結(jié)果為23，但最優(yōu)解為24.

基本思想:

選一個度量標(biāo)準(zhǔn)，根據(jù)這個標(biāo)準(zhǔn)進(jìn)行排序，以這個標(biāo)準(zhǔn)進(jìn)行輸出，每輸出一個，判斷是否符合約束條件。

背包問題:

1.選擇標(biāo)準(zhǔn):v(價值)/w(物品重量)

2.然后根據(jù)這個標(biāo)準(zhǔn)進(jìn)行排序得到一個最有解集

3.根據(jù)最優(yōu)解集，得到最大的價值

代碼:

package Recursion;

import java.util.Arrays;

import java.util.Scanner;

/**

* 背包貪心法

*

* @author ***

*

*/

public class Greedy {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.println("Please enter the number of objects(請輸入物品的數(shù)量：):");

int n = in.nextInt();

int[] w = new int[n]; // 物品重量數(shù)組

int[] v = new int[n]; // 物品價錢數(shù)組

System.out

.println("Now, please enter the weight of these objects(現(xiàn)在請輸入這些物品的重量：)");

for (int i = 0; i < n; i++) {

w[i] = in.nextInt();

}

System.out

.println("Now, please enter the value of these objects(現(xiàn)在請輸入這些物品的價值：)");

for (int i = 0; i < n; i++) {

v[i] = in.nextInt();

}

System.out

.println("Now, please enter the capacity of the pack(現(xiàn)在請輸入背包的容量：)");

int c = in.nextInt();

/**

* 按單位重量價值r[i] = v[i] / w[i]降序排列

*

* ps:排序用到了選擇排序，詳情請查看選擇排序

*/

double startTime = System.currentTimeMillis();

double[] r = new double[n];

int[] index = new int[n];

for (int i = 0; i < n; i++) {

r[i] = (double) v[i] / (double) w[i];

index[i] = i;

}

double temp = 0;

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {

if (r[i] < r[j]) {

temp = r[i];

r[i] = r[j];

r[j] = temp;

int x = index[i];

index[i] = index[j];

index[j] = x;

}

}

}

/**

* 排序后的重量和價值分別存到w1[]和v1[]中

*/

int[] w1 = new int[n];

int[] v1 = new int[n];

for (int i = 0; i < n; i++) {

w1[i] = w[index[i]];

v1[i] = v[index[i]];

}

/**

* 初始化解向量x[n]

*/

int[] x = new int[n];

for (int i = 0; i < n; i++) {

x[i] = 0;

}

/**

* 求解并打印解向量

*/

for (int i = 0; i < n; i++) {// 9 7 8 3 4

if (w1[i] < c) {

x[i] = 1;

c = c - w1[i];

}

}

System.out

.println("The solution vector is(解向量是：)" + Arrays.toString(x));

/**

* 根據(jù)解向量求出背包中存放物品的最大價值并打印

*/

int maxValue = 0;

for (int i = 0; i < n; i++) {

if (x[i] == 1)

maxValue += v1[i];

}

double endTime = System.currentTimeMillis();

System.out

.println("Now, the largest values of objects in the pack is(背包中物品的最大價值為：)"

+ maxValue);

System.out.println("Basic Statements take(基本語句用時)"

+ (endTime - startTime) + " milliseconds!");

}

}

總結(jié)

以上是生活随笔為你收集整理的贪心问题JAVA_java背包问题(贪心法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。