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

我会带着你远行 2024-02-17 14:38 23阅读 0赞

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

背包问题解决伪代码：

![Center][]

控制台实现代码：

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

结果：最大价值为15，第1/3/4/5件物品装入背包中。  
![Center 1][]

添加从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;
    			}
    }

txt结果：

![Center 2][]

[Knapsack.txt]: http://pan.baidu.com/s/1i3BlnSD
[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a66187b5346944daae6f0df6942cd7f5.png
[Center 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/4ba5e836df8a40c5a18338a21e89191f.png
[Center 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/93e6de547f1c4d098a2c92224cce5bab.png