背包问题——分数背包问题和0-1背包问题

实验III： 背包问题求解

本次实验拟解决生活中常见的问题之一：背包问题。该问题要求在一个物品集合中选择合适的物品放入背包，在放入背包中的物品总重量不超过背包容量的前提下，希望放入背包的物品总价值最大。根据是否允许部分物品放入背包的要求，背包问题可以分为分数背包问题和0-1背包问题。

对于分数背包问题，可以通过设计贪心算法得到问题实例的最优解。对于0-1背包问题，该问题已经被证明为NP-Hard，即不存在多项式时间算法那求解，但可以通过贪心算法得到问题的近似解，或者通过蛮力法、动态规划法得到问题的最优解。本次实验需要学生根据所给问题限制条件采取有效算法解决背包问题，并能分析各个算法所使用的算法设计技术和时间复杂度。下列基本要求必须完成：

1. 设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面；
2. 能够人工输入一个背包问题具体实例，涉及物品个数、每个物品的重量和价值，以及背包容量；
3. 设计一个贪心算法求解分数背包问题给定实例的最优解，并分析算法的时间复杂度；
4. 设计一个贪心算法求解0-1背包问题给定实例的近似解，请提供一个反例判断该算法不能总是能够给出最优解，并证明算法的解和最优解的值的比值大于等于1/2。
5. 设计一个蛮力法算法求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；
6. 设计一个动态规划算法求解求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；
7. 使用记忆功能改进6中的动态规划算法，尽量避免不必要的填表计算。
8. 对比以上方法的执行效率，是否可以得到最优解。

Bagquestion .java

package com;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

import javax.swing.JOptionPane;
import javax.swing.JTextArea;



public class Bagquestion {
	
	
	public void choose(int num) {
//		Scanner scanner = new Scanner(System.in);

        // 输入物品个数
//        System.out.print("请输入物品个数：");
//        int itemCount = scanner.nextInt();
        int itemCount = Integer.parseInt(JOptionPane.showInputDialog("请输入物品个数:"));

        // 输入每个物品的重量和价值
        // 输入每个物品的重量和价值
        int[][] items = new int[itemCount][2];
        JTextArea textArea = new JTextArea(10, 20);
        JOptionPane.showOptionDialog(null, textArea, "请输入每个物品的重量和价值,换行继续", JOptionPane.OK_CANCEL_OPTION, JOptionPane.INFORMATION_MESSAGE, null, null, null);
        String inputs = textArea.getText();
        String[] inputsArray = inputs.split("\n");

        for (int i = 0; i < itemCount; i++) {
            String[] itemValues = inputsArray[i].split(" ");
            items[i][0] = Integer.parseInt(itemValues[0]);
            items[i][1] = Integer.parseInt(itemValues[1]);
        }

        // 输入背包容量
        int capacity = Integer.parseInt(JOptionPane.showInputDialog("请输入背包容量："));

        //   scanner.close();
       
        
        switch(num) {
        	case 1:
        		//贪心分数背包
        		double maxTotalValue = fractionalKnapsack(items, capacity);
                JOptionPane.showMessageDialog(null, "贪心分数背包问题的最优解为：" + maxTotalValue, "结果", JOptionPane.INFORMATION_MESSAGE);
        		break;
        	case 2:
        		//贪心01背包
        		int maxTotalValue1 = knapsackApproximation(items, capacity);      
        		JOptionPane.showMessageDialog(null, "贪心0-1背包问题的近似解为：" + maxTotalValue1, "结果", JOptionPane.INFORMATION_MESSAGE);
        		break;
        	case 3: