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

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

背包问题解决伪代码：

控制台实现代码：

package seven.suanfa.whp;

public class Knapsack {

	/**
	 * @王海平
	 */
	int count=15;  //容量为15
	int weight[]={4,12,1,2,1}; //物品的重量
	int value[]={10,4,2,2,1};	//物品的价值
	int result[]={-1,-1,-1,-1,-1};//初始化背包
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Knapsack ks=new Knapsack();
		System.out.println(ks.Knapsacountk(4,15));
		ks.print();
	
		
	}
	public void print(){
		for(int i=0;i<result.length;i++)
		{
			System.out.println(result[i]);
		}
	}
	public int Knapsacountk(int n ,int count)
	{
		if(n==-1||count==0)
			return 0;
		int tmp1=Knapsacountk(n-1,count);
		if(weight[n]>count)
		{
			result[n]=0;
			return tmp1;
		}
		int tmp2=value[n]+Knapsacountk(n-1,count-weight[n]);
		if(tmp1>tmp2)
		{
			result[n]=0;
			return tmp1;
		}
		result[n]=1;
		return tmp2;	
	}

}

添加从txt中读取和写入txt代码。

package seven.suanfa.whp;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Knapsack {

	/**
	 * @王海平
	 */
	static int count=0;  //容量为15
	static int weight[]={0,0,0,0,0}; //物品的重量
	static int value[]={0,0,0,0,0};	//物品的价值
	static int result[]={-1,-1,-1,-1,-1};//初始化背包
	public static void main(String[] args) {
		String path = "txt/Knapsack.txt";
		ArrayList<Integer> list = read(path);
		
		for(int i=2,j=0;i<list.size();i=i+2,j++){
			
			weight[j]=list.get(i);
		}
		for(int i=3,j=0;i<list.size();i=i+2,j++){
			
			value[j]=list.get(i);
		}
		//控制台打印
		Knapsack ks=new Knapsack();
		System.out.println(ks.Knapsacountk(list.get(1)-1,list.get(0)));
		ks.print();
		//写入txt
		ks.write(result);
		
	}
	
	//控制台打印
	public void print(){
		for(int i=0;i<result.length;i++)
		{
			System.out.println(result[i]);
		}
	}
	//写入txt
	public  void write(int[] list) {
		File f = new File("txt/KnapsackResult.txt");
		FileOutputStream fou = null;
		try {
			fou = new FileOutputStream(f, true);// true,设置可追加
			for (int i = 0; i < list.length; i++) {
				String s = String.valueOf(list[i]);
				String a = "" + s + "\t\n";
				// byte []bytes=new byte[1024];
				// 如何把string转换byte数组
				fou.write(a.getBytes());

			}
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
		} finally {
			try {
				fou.close();
			} catch (Exception e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
	public int Knapsacountk(int n ,int count)
	{
		if(n==-1||count==0)
			return 0;
		int tmp1=Knapsacountk(n-1,count);
		if(weight[n]>count)
		{
			result[n]=0;
			return tmp1;
		}
		int tmp2=value[n]+Knapsacountk(n-1,count-weight[n]);
		if(tmp1>tmp2)
		{
			result[n]=0;
			return tmp1;
		}
		result[n]=1;
		return tmp2;	
	}
	// 读取文件到Arraylist 数组
			public static ArrayList read(String path) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				BufferedReader input = null;
				try {
					FileReader in = new FileReader(path);
					input = new BufferedReader(in);
					String ss;
					try {
						while ((ss = input.readLine()) != null) {
							String[] s = (ss.split("  "));
							for (int i = 0; i < s.length; i++) {
								list.add(Integer.parseInt(s[i].trim())); // 将String
																			// s中的内容添加到动态数组中
							}

						}
					} catch (IOException e) {
						// TODO 自动生成的 catch 块
						e.printStackTrace();
					}
					in.close();
					input.close();
				} catch (Exception e) {
					// TODO 自动生成的 catch 块
					e.printStackTrace();
				}

				return list;
			}
}

第7周作业1——背包问题,布布扣,bubuko.com

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

原文：http://blog.csdn.net/wanghaiping1993/article/details/24348581