首页 > 其他分享 >8.14扣...

8.14扣...

时间:2024-08-18 20:51:55浏览次数:13  
标签:... 背包 容量 int Thing packMoneyArr 8.14 价值

贪心算法求背包问题

1.定义数组 int[] packMoneyArr  用于存储行遍历的不同背包容量下的价值最大值

2.定义物品数组   Thing thing = new Thing(curVo, curMoney);  用于计算在每一个最大值对应的固定容量的包的情况下,其容量还能否支撑其添加新的物品,若能添加,则将添加后的值和原值比较,更新最大值;

package 背包问题之贪心算法;
import java.util.Scanner;
public class Package {
    /*
     * 背包总容量6
     *
     * 三组数据
     * 容量3    价值5
     * 容量2    价值4
     * 容量4    价值2
     *
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        /*
         * 背包容量
         *
         * */
        System.out.print("请输入背包最大重量:");
        int packMax = scanner.nextInt();
        System.out.print("请输入背包容纳物品数:");
        int n = scanner.nextInt();
        Thing[] things = new Thing[n];
        for (int i = 0; i < n; i++) {
            System.out.print("请输入第"+(i+1)+"个商品的重量");
            int curVo = scanner.nextInt();
            System.out.print("请输入第"+(i+1)+"个商品的价值");
            int curMoney = scanner.nextInt();
            Thing thing = new Thing(curVo, curMoney);
            things[i] = thing;
        }
        /*定义数组,保存背包每一个体积对应的价值*/
        int[] packMoneyArr = new int[packMax + 1];
        //存储每个背包容量的最大值数组
        for (int j = 0; j < n; j++) {
        //按行遍历,得到不同容量背包对于第I个物品的存储情况
            for (int k = packMax; k > 0; k--) {
                int max = packMoneyArr[k];
                 // 当前容量k的最大价值初始化为之前记录的最大价值
                int packLeft = k - things[j].vo;//剩余容量
                if (packLeft >= 0
                        && max < things[j].money + packMoneyArr[packLeft]) { 
                       //剩余容量大于0 且 最大值小于当前物品的价值加上之前背包内物品的价值
                    max = things[j].money + packMoneyArr[packLeft];
                  //将最大值替换为原本物品价值+可放入物品价值的总和
                }
                if (max > packMoneyArr[k]) {
                 // 如果更新后的最大价值大于当前容量k之前的最大价值,则更新
                    packMoneyArr[k] = max;
                }
            }
        }
        System.out.println(packMoneyArr[packMax]);
    }
}

class Thing {
    int vo;// 容量
    int money;// 价值

    public Thing(int vo, int money) {
        this.vo = vo;
        this.money = money;
    }
}

标签:...,背包,容量,int,Thing,packMoneyArr,8.14,价值
From: https://blog.csdn.net/weixin_51721783/article/details/141174199

相关文章

  • UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xaf...--web逆向execjs读取j
    背景做web逆向的时候我们通常是纯python模拟js思路或js+python直接逆向,第二种情况下我们要先获取到想要的js代码,js文件内测试接口后,通过python中的`execjs`模块实现相应接口的调用。通常我们会直接从网站扣下需要的代码(分析后硬扣或通过webpack),然后稍加删改和补环境就直接使用......
  • Datawhale X 魔搭 AI0夏令营 魔搭-AIGC文生图方向 Tsak 3 就要完成了...
    本文为AI方向小白记录暑期参加魔搭夏令营-AIGC文生图方向的Task01    报名赛事链接:可图Kolors-LoRA风格故事挑战赛_创新应用大赛_天池大赛-阿里云天池的赛制    欢迎所有小白,大神前来交流学习。一.初识ComfyUI    1.1什么是ComfyUI      ......
  • python判断语句之if语句、比较和逻辑运算符、if...else...语句、if...elif...else语句
    文章目录1.介绍1.1顺序语句1.2判断语句1.3循环语句2.if语句的基本格式2.1判断语句介绍2.2程序中的判断2.3if语句的基本格式3.比较和逻辑运算符3.1比较运算符3.2逻辑运算符4.if...else...语句4.1if...else...的语法格式4.2实例5.if...elif...else...语......
  • 【-..-.-.-----..-./-...-.----.---.-】-----/---../.-.-.-/.----/...../.-.-.-/..---
    -----/---../.----/...../-..-.-.-----..-./-...-.----.---.--.--..-..--.-../-.-.--.-------./--------...--.-.-..---.--..-.-./--..-.----..-.-/--...---.-.-.../--.-.--.-..--../--------...--.-.--........-.-./----.-..----.-./--....-..-..-./--.---.-......./--........
  • 报表的多行业应用!用工具做报表省了我不少事...
    一、什么是报表?说起报表,你不会还停留在Excel报表的层面上吧? 传统的报表一般都是基于Excel制作的,主要面向业务人员、开发人员等,也有一些公司会自己去开发设计,只不过周期较长,耗费人力多。现在的报表早已经不同于往日,它们可以将不同的数据源进行整合,然后生成所需要的各种类型报表......
  • 2024.8.14 DP Round 2
    A.storeStatement:有\(n(1\len\le100)\)个果盘,其中第\(i\)个果盘有\(a_i\)个水果,容量是\(b_i(a_i\leb_i\le100)\)。一次操作可以将一个水果从一个果盘放到另一个果盘中,现在要将所有水果放到最少的盘子中,问最少要用多少盘子以及最少需要多少操作。Solution:第一......
  • day43-dynamic programming-part10-8.14
    tasksfortoday:1.300.最长递增子序列2.674.最长连续递增序列3.718.最长重复子数组--------------------------------------------------------------------------1.300.最长递增子序列Inthispractice,notethemeaningofthedplist:whichis:dp[i]signifi......
  • 2024.8.14 总结(集训)
    依然是TQX来讲字符串。/bx/bx/bx属于是两个上午速通字符串里一些重要的内容。上课时只有manacher和PAM是我有点听懂了的。于是下午看TQX的博客学了PAM,看之前看过的博客复习了下SAM,给why讲了些、和他讨论了PAM,AC了洛谷上的PAM板子,看TQX的PPT学了manache......
  • 2024.8.14 test
    A一棵树,你每天可以选择不超过\(m\)个祖先都被选择的点,问最少多少天选完。\(n\le10^5\)。考虑贪心,每次选出子树深度最大的\(m\)个点或子树大小最大的\(m\)个点都是对的。B一棵树\(n\le5e5\),选若干出来,对于每个点,如果其儿子有选,那么不能被选,否则其有\(p_u\)概率被选......
  • 8.14 PTA练习
    3-11求一元二次方程的根本题目要求一元二次方程ax2+bx+c=0的根,结果保留2位小数。(注意:0.00会在gcc下被输出为-0.00,需要做特殊处理,输出正确的0.00。)输入格式:输入在一行中给出3个浮点系数a、b、c,中间用空格分开。输出格式:根据系数情况,输出不同结果:1)如果方程有两个不相等的......