1 .题目

本次实验拟解决生活中常见的问题之一：背包问题。该问题要求在一个物品集合中选择合适的物品放入背包，在放入背包中的物品总重量不超过背包容量的前提下，希望放入背包的物品总价值最大。根据是否允许部分物品放入背包的要求，背包问题可以分为分数背包问题和0-1背包问题。
对于分数背包问题，可以通过设计贪心算法得到问题实例的最优解。对于0-1背包问题，该问题已经被证明为NP-Hard，即不存在多项式时间算法那求解，但可以通过贪心算法得到问题的近似解，或者通过蛮力法、动态规划法得到问题的最优解。本次实验需要学生根据所给问题限制条件采取有效算法解决背包问题，并能分析各个算法所使用的算法设计技术和时间复杂度。下列基本要求必须完成：

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

2.求解步骤

1、设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面；

2、能够人工输入一个背包问题具体实例，涉及物品个数、每个物品的重量和价值，以及背包容量；

3、设计一个贪心算法求解分数背包问题给定实例的最优解，并分析算法的时间复杂度；

4、设计一个贪心算法求解0-1背包问题给定实例的近似解，请提供一个反例判断该算法不能总是能够给出最优解，并证明算法的解和最优解的值的比值大于等于1/2。

5、设计一个蛮力法算法求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；

6、设计一个动态规划算法求解求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；

7、使用记忆功能改进6中的动态规划算法，尽量避免不必要的填表计算。

3.实现代码

package com.exp3;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author 郑万富
 * @className Knapsack
 * @date 2021/11/19 17:35
 */
public class Knapsack {
    //背包问题基本属性
    private int capacity;//背包总容量
    private int num;//物品数量
    private int[] w;//物品重量
    private int[] v;//物品价值
    private int[][] tv;//物品总价值（构造二维表）
    private int[][] memory;//背包记忆表
    //蛮力法
    private int[] id;//序号
    private int[] select;//是否装入 1装入 0 不装
    //分隔会产生小数,所以使用实数类型
    private float[] ratio;//性价比=价格/体积
    private float[] rate;//使用率：1代表物品完整放入，小于1代表被分割后放入
    //最优解比较
    private float nice1;//贪心算法0-1背包近似解
    private float nice2;//最优解
    public static void main(String[] args) {
        choice();
    }
    //5、设计一个蛮力法算法求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；
    void decide(int select[], int n) {
        for (int i = 0; i < n; i++) {
            if (select[i] == 1) {
                select[i] = 0;
            } else {
                select[i] = 1;
                break;
            }
        }
    }
    void brute(int id[], int select[], int n, int w[], int v[], int capacity) {
        int maxi = 0, maxsumw = 0, maxsumv = 0;
        int pw = (int) Math.pow(2.0, n);
        System.out.println("蛮力法求解0-1背包问题");
        System.out.println("序号\t选中物品\t\t总重量\t总价值\t是否装入\t");
        for (int i = 0; i < pw; i++) {
            System.out.print(" " + (i + 1) + "\t\t{");
            int sumw = 0, sumv = 0;
            for (int j = 0; j < n; j++) {
                if (select[j] == 1) {
                    sumw += w[j];
                    sumv += v[j];
                    System.out.print(id[j]);
                }
            }
            System.out.print("}\t\t"+sumw+"\t\t"+sumv+"\t");
            if (sumw <= capacity) {
                System.out.println("是");
                if (sumv > maxsumv) {            //判断是否为当前最优方案
                    maxi = i + 1;
                    maxsumw = sumw;
                    maxsumv = sumv;
                }
            } else {
                System.out.println("否");
            }
            decide(select, n);
        }
        System.out.println("最佳方案为：序号" + maxi + "总重量" + maxsumw + "总价值：" + maxsumv);
    }
    //4、设计一个贪心算法求解0-1背包问题给定实例的近似解，请提供一个反例判断该算法不能总是能够给出最优解，并证明算法的解和最优解的值的比值大于等于1/2。
    public void greedKnapsack0_1() {
        //背包容量capacity
        downRatio(ratio, w, v);
        int sum_w = 0;
        int i = 0;
        for (i = 0; i < num; i++) {
            //不超过背包容量
            if (this.w[i] <= capacity) {
                nice1++;
                rate[i] = 1;
                sum_w += w[i];//物品不断增加
                capacity -= w[i];//背包容量不断减少
                System.out.println("选择重量:" + w[i] + "质量:" + v[i] + "性价比:" + ratio[i] + "的物品装入背包,装入比例:" + rate[i]);
            } else {
                //装不下就退出
                break;
            }
        }
        //背包虽有容量,但是物品不在分割
    }
    //3、设计一个贪心算法求解分数背包问题给定实例的最优解，并分析算法的时间复杂度；
    public void greedKnapsack() {
        //背包容量capacity
        downRatio(ratio, w, v);
        int sum_w = 0;
        int i = 0;
        for (i = 0; i < num; i++) {
            //不超过背包容量
            if (this.w[i] <= capacity) {
                nice2++;
                rate[i] = 1;
                sum_w += w[i];//物品不断增加
                capacity -= w[i];//背包容量不断减少
                System.out.println("选择重量:" + w[i] + "质量:" + v[i] + "性价比:" + ratio[i] + "的物品装入背包,装入比例:" + rate[i]);
            } else {
                //装不下就退出
                break;
            }
        }
        //如果物品没有装完
        if (i < num) {
            nice2++;
            //  背包容量还剩capacity(上一步不断减小后的结果),计算出未装入的物品能装多少的比例
            rate[i] = (float) capacity / w[i];
            //分割放入背包
            sum_w += rate[i] * w[i];
            System.out.println("选择重量:" + w[i] + "质量:" + v[i] + "性价比:" + ratio[i] + "的物品装入背包,装入比例:" + rate[i]);
        }
    }
    //写一个方法对数组降序返回性价比数组(顺便更新质量\价格同步)
    public float[] downRatio(float[] ratio, int[] w, int[] v) {
        int len = ratio.length - 1;
        while (true) {
            int last = 0;//表示最后一次交换索引的位置
            for (int i = 0; i < len; i++) {
                if (ratio[i] < ratio[i + 1]) {
                    swapFloat(ratio, i, i + 1);
                    swapInt(w, i, i + 1);
                    swapInt(v, i, i + 1);
                    last = i;
                }
            }
            len = last;
            if (len == 0) {
                break;
            }
        }
        System.out.println("物品性价比降序输出:" + Arrays.toString(ratio));
        System.out.println("物品重量随性价比更新:" + Arrays.toString(w));
        System.out.println("物品价值随性价比更新:" + Arrays.toString(v));
        return rate;
    }
    //写一个方法交换数组元素
    public static void swapFloat(float[] array, int i, int j) {
        float t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    //写一个方法交换数组元素
    public static void swapInt(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    /**
     * 设计一个动态规划算法求解求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度；
     */
    public void dynamic() {
        //最大价值数组tv
      //  this.tv = new int[this.v.length + 1][this.capacity + 1];
        this.tv = new int[this.v.length + 1][this.capacity + 1];
     //   this.memory = new int[this.v.length + 1][this.capacity + 1];
        this.memory = new int[this.v.length + 1][this.capacity + 1];
        //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
        for (int i = 0; i < v.length; i++) {
            tv[i][0] = 0; //将第一列设置为0
        }
        for (int i = 0; i < tv[0].length; i++) {
            tv[0][i] = 0; //将第一行设置0
        }
        //空物品和空容量默认为0不处理
        for (int i = 1; i < tv.length; i++) {
            for (int j = 1; j < tv[0].length; j++) {
                //第一种情况：当准备新增的物品容量大于背包容量时，使用上一格
                if (this.w[i - 1] > j) {
                    tv[i][j] = tv[i - 1][j];
                } else {
                    //  tv[i][j] = Math.max(tv[i - 1][j], v[i - 1] + tv[i - 1][j - w[i - 1]]);
                    if (tv[i - 1][j] < v[i - 1] + tv[i - 1][j - w[i - 1]]) {
                        tv[i][j] = v[i - 1] + tv[i - 1][j - w[i - 1]];
                       //记忆功能
                        memory[i][j] = 1;
                    } else {
                        tv[i][j] = tv[i - 1][j];
                    }
                }
            }
        }
        //输出一下v 看看目前的情况
      /*
        for (int i = 0; i < tv.length; i++) {
            for (int j = 0; j < tv[i].length; j++) {
                System.out.print(tv[i][j] + " ");
            }
            System.out.println();
        }*/
        //记忆输出
        int row = memory.length - 1;//行最大下标
        int col = memory[0].length - 1;//列最大下标
        while (row > 0 && col > 0) {
            if (memory[row][col] == 1) {
                System.out.println("将物品" + row + "放入背包");
                col -= w[row - 1];
            }
            row--;
        }
    }
    /**
     * 能够人工输入一个背包问题具体实例，涉及物品个数、每个物品的重量和价值，以及背包容量；
     */
    public void initKnapsackTest() {
        this.num=5;
        //物品重量数组
        this.w= new int[]{600, 250, 200, 100, 300};;
        //物品价值数组
        this.v = new int[]{60,10,36,16,45};
        //性价比
        ratio = new float[this.num];
        //装入比例
        rate = new float[this.num];
        //物品编号
        id = new int[this.num];
        //物品选择
        select = new int[this.num];
        for (int i = 0; i < this.w.length; i++) {
            //计算每个物品的性价比=价格/重量
            this.ratio[i] = (float) v[i] / w[i];
            //初始化每个物品的装入比例
            this.rate[i] = 0;
            //物品编号
            id[i] = i + 1;
            //刚开始都未装入背包
            select[i] = 0;
        }
        this.capacity = 800;
        //输出物品重量
        System.out.println("物品重量:" + Arrays.toString(this.w));
        //输出物品的价值
        System.out.println("物品价值:" + Arrays.toString(this.v));
        //输出物品性价比
        System.out.println("物品性价比:" + Arrays.toString(this.ratio));
        System.out.println("背包总容量为:" + this.capacity);
    }
    public void initKnapsack() {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入物品个数：");
        this.num = input.nextInt();
        //物品重量数组
        this.w = new int[this.num];
        //物品价值数组
        this.v = new int[this.num];
        //性价比
        ratio = new float[this.num];
        //装入比例
        rate = new float[this.num];
        //物品编号
        id = new int[this.num];
        //物品选择
        select = new int[this.num];
        System.out.println("请输入每个物品的重量和价值:");
        for (int i = 0; i < this.w.length; i++) {
            System.out.println("物品" + (i + 1) + "的重量: ");
            this.w[i] = input.nextInt();
            System.out.println("物品" + (i + 1) + "的价值: ");
            this.v[i] = input.nextInt();
            //计算每个物品的性价比=价格/重量
            this.ratio[i] = (float) v[i] / w[i];
            //初始化每个物品的装入比例
            this.rate[i] = 0;
            //物品编号
            id[i] = i + 1;
            //刚开始都未装入背包
            select[i] = 0;
        }
        System.out.println("请输入背包容量:");
        this.capacity = input.nextInt();
        //输出物品重量
        System.out.println("物品重量:" + Arrays.toString(this.w));
        //输出物品的价值
        System.out.println("物品价值:" + Arrays.toString(this.v));
        //输出物品性价比
        System.out.println("物品性价比:" + Arrays.toString(this.ratio));
        //背包容量capacity
        downRatio(ratio, w, v);
        System.out.println("背包总容量为:" + this.capacity);
    }
    public static void miniMenu() {
        System.out.println("|------------实验III：背包问题求解----------|");
        System.out.println("             1.初始化背包问题");
        System.out.println("             2.贪心算法求解分数背包问题最优解");
        System.out.println("             3.贪心算法求解0-1背包问题近似解");
        System.out.println("             4.蛮力法算法求解0-1背包问题最优解");
        System.out.println("             5.动态规划算法(含记忆功能)求解求解0-1背包问题最优解");
        System.out.println("             6.返回主菜单");
        System.out.println("             0.退出程序");
        System.out.println("|---------------------------------------|");
    }
    public static void moreMenu() {
        System.out.println("|------------------------------------------------------实验III：背包问题求解--------------------------------------------------------|");
        System.out.println("        1、设计一个交互界面（例如菜单）供用户选择，如果可能，最好是一个图形化用户界面");
        System.out.println("        2、能够人工输入一个背包问题具体实例，涉及物品个数、每个物品的重量和价值，以及背包容量");
        System.out.println("        3、设计一个贪心算法求解分数背包问题给定实例的最优解，并分析算法的时间复杂度");
        System.out.println("        4、设计一个贪心算法求解0-1背包问题给定实例的近似解，请提供一个反例判断该算法不能总是能够给出最优解，并证明算法的解和最优解的值的比值大于等于1/2");
        System.out.println("        5、设计一个蛮力法算法求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度");
        System.out.println("        6、设计一个动态规划算法求解求解0-1背包问题给定实例的最优解，并分析算法的时间复杂度");
        System.out.println("        7、使用记忆功能改进6中的动态规划算法，尽量避免不必要的填表计算");
        System.out.println("|-------------------------------------------------------------------------------------------------------------------------------|");
    }
    public static void choice() {
        Scanner sc = new Scanner(System.in);
        //解决对象
        Knapsack knapsack = new Knapsack();
        while (true) {
            miniMenu();
            System.out.println("请输入你要执行的序号（0退出）：");
            int choice = sc.nextInt();
            switch (choice) {
                case 1:
                    knapsack.initKnapsackTest();
                    continue;
                case 2:
                    knapsack.greedKnapsack();
                    break;
                case 3:
                    knapsack.greedKnapsack0_1();
                    break;
                case 4:
                    knapsack.brute(knapsack.id,knapsack.select, knapsack.num, knapsack.w, knapsack.v, knapsack.capacity);
                    break;
                case 5:
                    knapsack.dynamic();
                    break;
                case 6:
                    moreMenu();
                    break;
                case 0:
                    knapsack.initKnapsackTest();
                    System.out.println("---------------------------------------------------");
                    knapsack.greedKnapsack0_1();
                    System.out.println("--------------------------------------------------");
                    knapsack.initKnapsackTest();
                    System.out.println("---------------------------------------------------");
                    knapsack.greedKnapsack();
                    System.out.println("---------------------------------------------------");
                    System.out.println("贪心算法的近似解和最优解的值的比值:"+(knapsack.nice1)/ knapsack.nice2);
                    System.out.println("正在退出程序...");
                    break;
                default:
                    System.out.println("输入错误，请重新输入：");
                    break;
            }
            break;
        }
    }
}

算法分析与程序设计基础

3、实验III：背包问题求解

1 .题目

2.求解步骤

3.实现代码