(java)通过超市购物游戏案例的分析,掌握动态规划0-1背包问题的实际应用 。

输入:超市有很多种商品,让你从超市选购商品,每个品种只能选购一个,是最后都能装入承重量不超过7kg的纸袋子中,并且商品的价值最大,商品信息如下: 

商品编码

1

2

3

4

5

6

7

8

9

10

商品名称

牙膏

啤酒

牛奶

面包

香皂

台灯

面粉

大米

酱油

纸巾

重量g

300

500

200

250

250

1000

4000

2000

800

200

价值元

12

3

2.5

6

5

20

8

6

7

9

要求输入数据从文本文件或格式文件中导入,或程序运行时直接输入。

输出:所选商品信息形式如下

商品编码

商品名称

重量

价值

1

牙膏

300

12

2

啤酒

500

3

3

牛奶

200

2.5

4

面包

250

6

5

香皂

250

5

6

台灯

1000

20

由于时间原因,原理后续补上。。。

代码如下:

package com.ag.algorithm;

/**
 * 动态规划解决0-1背包问题
 *
 */
public class knapsbag {
    static String[] name={"牙膏","啤酒","牛奶","面包", "香皂","台灯","面粉","大米","酱油","纸巾"};
    static int[] w = {300, 500, 200, 250, 250, 1000, 4000, 2000, 800, 200};
    static double[] p = {12, 3, 2.5, 6, 5, 20, 8, 6, 7, 9};
    static int bagweight=7000;
    static  int value0=0;
      static  int wlen =w.length;   //物品的个数
    static  double dp[][]=new double[wlen+1][bagweight+1];  //初始化dp数组,前i个商品的总价值;
    static int[] item=new int[dp.length+1];/*用于对应name*/
    public static void main(String[] args) {
      findmax(w,p,bagweight);//调用方法
        print();
   System.out.println(findmax(w,p,bagweight));
    }

    /**
     *
     *
     * 动态规划求出最大值
     * @param w
     * @param p
     * @param bagweight
     * @return
     */
    private static double findmax(int[] w, double[] p, int bagweight) {
        for (int i = 0; i <=w.length ; i++) {
              dp[i][0]=value0;
        }
        for (int i = 1; i <=wlen ; i++) {    //遍历物品
            for (int j = 1; j <=bagweight ; j++) {  //遍历背包的容量
                  if(j<w[i-1]){
                      dp[i][j]=dp[i-1][j];   //不拿物品
                  }else
                  {
                      dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+p[i-1]);
                  }
            }
        }
        return dp[wlen][bagweight];
    }

    /**
     * 输出商品的名字,重量和价格
     *
     */
    private static void print() {
        System.out.println("商品编码 名称     重量     价格");
        for (int i = 1; i <dp.length; i++)		{
            double a=item[i];
            if(a==0){
                System.out.println(i-1+"       " +  name[i-1]+"     "+w[i-1]+"    "+p[i-1]);
            }

        }
    }



}

上一篇:爬虫实战—豆瓣250榜单的爬取


下一篇:python中字典与json的联系与区别