0-1背包问题(贪心法)

背包问题

有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30

贪心算法描述:

1.改变数组w和v的排列顺序,使其按单位重量价值v[i]/w[i]降序排列; 2.将数组x[n]初始化为0; //初始化向量

  1. i=1; 4.循环直到(w[i]>C); 4.1 x[i]=1; 4.2 C=C-w[i]; 4.3 i++;
  2. x[i]=C/w[i]; **/
public class Package2 {

        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入物品的数量:");
            int n = in.nextInt();
            int[] w = new int[n];
            int[] v = new int[n];
            System.out.println("现在请输入这些物品的重量:");
            for (int i = 0; i < n; i++) {
                w[i] = in.nextInt();
            }
            System.out.println("现在请输入这些物品的价值:");
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
            }
            System.out.println("现在请输入背包的容量:");
            int c = in.nextInt();
            /**
             *按单位重量价值r[i]=v[i]/w[i]降序排列
             */

            double[] r = new double[n];
            int[] index = new int[n];
            for (int i = 0; i < n; i++) {
                r[i] = (double) v[i] / (double) w[i];
                index[i] = i;
            }
            double temp = 0;
            //降序排列
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (r[i] < r[j]) {
                        temp = r[i];
                        r[i] = r[j];
                        r[j] = temp;
                        //交换i,j的下标
                        int x = index[i];
                        index[i] = index[j];
                        index[j] = x;
                    }
                }
            }
            /**
             *排序后的重量和价值分别存到w1[]和v1[]中
             */
            int[] w1 = new int[n];
            int[] v1 = new int[n];
            int maxValue = 0;
            for (int i = 0; i < n; i++) {
                w1[i] = w[index[i]];
                v1[i] = v[index[i]];
            }
            System.out.println(Arrays.toString(w1));
            System.out.println(Arrays.toString(v1));
            /**
             *初始化解向量x[n]
             */
            int[] x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = 0;
            }
            /**
             *求解并打印解向量
             */
            for (int i = 0; i < n; i++) {
                if (w1[i] < c) {
                    x[i] = 1;
                    c = c - w1[i];
                    maxValue += v1[i];
                }
                else{
                    x[i] = c/w[index[i]];
                    maxValue += x[i]*v[index[i]];
                    //break; 去掉这个就好
                }


            }



            System.out.println("解向量是:" + Arrays.toString(x));
            /**
             *根据解向量求出背包中存放物品的最大价值并打印
             */



            System.out.println("背包中物品的最大价值为:" + maxValue);

        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

1.2K13
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3247
来自专栏绿巨人专栏

函数式编程 : 一个程序猿进化的故事

3649
来自专栏数据之美

浮点数加法引发的问题:浮点数的二进制表示

1、问题: 之前有同学问过这样一个问题: echo|awk '{print 3.99 -1.19 -2.80}' 4.44089e-16 类似的问题还...

2389
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3605
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

4207
来自专栏牛客网

深信服面试 C++/云计算面经

2465
来自专栏小二的折腾日记

LeetCode-55-Jump-Game

由题可知,数组的位置表示从该位置可以像前跳的步数,看最终能否跳到结尾。乍一看,这像是一个动态规划的问题,dp数组内存储每一个位置能够走的最远的位置,但是仔细一想...

1563
来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

783
来自专栏软件开发 -- 分享 互助 成长

01背包及其变种(物品无限背包、恰好装满背包)

一、01背包问题   01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解将那...

1.8K10

扫码关注云+社区

领取腾讯云代金券