第7周作业1——背包问题

（1）背包问题。对上文中提到的背包问题提供的表1（数据文件下载Knapsack.txt，第一行为背包总重量15，物品数量5；第2-6行，分别为第1-5件物品的重量与价值），W=15，编程计算最终背包所装物品的编号、总重量与总价值。要求能够把构造的二维表格输出到文件KnapsackResult.txt中。

package 算法作业;

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.Scanner;

public class Knapsack {

public static void main(String[] args) {
Scanner scanner = new Scanner(Knapsack.class.getResourceAsStream("d:/Knapsack.txt"));
try {
FileWriter out = new FileWriter(new File("d:/KnapsackResult.txt"));
//第一行为背包总重量15，物品数量5
int W=scanner.nextInt(), n=scanner.nextInt();
int wv[][] = new int[n][2];
for(int i=0; i<n; i++){
wv[i][0]=scanner.nextInt();
wv[i][1]=scanner.nextInt();
}

Knapsack knapsack = new Knapsack();
int K[][] = knapsack.getArray(W, n, wv);

//将背包问题的二维表格保存到问文件KnapsackResult.txt
for(int w=0; w<=W; w++){
for(int j=0; j<=n; j++){
out.write(K[w][j]+"\t");
}
out.write("\r\n");
}
out.close();
scanner.close();

int[] isTaked = getIsTaked(wv, K, W, n);
System.err.println("放入背包中的物品总重量为: "+isTaked[0]);

System.err.println("放入背包中的物品编号为: ");
for(int No=1; No<isTaked.length; No++){
if(isTaked[No] == 1) System.err.print(No + "\t");
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}





}
public int[][] getArray(int W, int n, int wv[][]){

int[][] K = new int[W+1][n+1];

for(int j=1; j<=n; j++){
for(int w=1; w<=W; w++){
int maxW = wv[j-1][0];
if(maxW>w){
K[w][j] = K[w][j-1];
}else{
K[w][j] = max(K[w][j - 1],K[w - maxW][j - 1]+wv[j - 1][1]);
}
}
}
return K;
}

public int max(int a, int b){
return a>b ? a : b;
}

public static int[] getIsTaked(int[][] wv,int[][] K,int W,int n){

int isTaked[]=new int[n+1];

int w = W;
for(int j=n;j>0;j--){
if(K[w][j]>K[w][j-1]){
isTaked[j]=1;
w = w - wv[j-1][0];
if(w<0) break;
}
}

int sumW=0;
for(int j=1;j<=n;j++){
if(isTaked[j]==1){
sumW+=wv[j-1][0];
}
}
isTaked[0] = sumW;

return isTaked;
}

}