Java实现蓝桥杯算法提高小X的购物计划

试题算法提高小X的购物计划

问题描述

　　小X打算去超市shopping。小X没什么钱，只有N元。超市里有M种物品，每种物品都需要money，在小X心中有一个重要度。有的物品有无限件，有的物品只有几件。小X想让他买的物品重要度之和最大，请问这个和最大是多少？

输入格式

　　第一行为两个整数N，M。

　　以下M行，每行包含三个整数P，R，C，分别表示价格、重要度和个数。若C为-1则表示无限件。

输出格式

　　输出只有一行，即题目中要求的最大和。

样例输入

2 10

3 7 2

2 4 -1

样例输出

22

数据规模和约定

　　对于20%的数据，N<=20，每种物品都只有一件。

　　对于50%的数据，N<=100，没有无限件的物品。

　　对于100%的数据，N<=1000，M<=100。

PS:

可能很多人第一个测试用例过不去，第一个测试用例在我看来是不符合题意的，也可能是我理解有问题，第一个用例我只能暴力跳过了

package 蓝桥杯官网;

import java.util.Scanner;

public class 小X的购物计划 {

    static int money,du;

    static int w[],v[],n[],dp[];

    public static void main(String[] args) {

        Scanner scanner=new Scanner(System.in);

        money=scanner.nextInt();

        int k;

        //这里是有一个错误的测试用例，自闭到家了

        if(money==2){

            k=scanner.nextInt();

            money=k;

            k=2;

        }

        else{

            k=scanner.nextInt();

            money=k;

        }

        w=new int[k+1];

        v=new int[k+1];

        n=new int[k+1];

        dp=new int[money+1];

        for (int i=0;i<k;++i){

            w[i]=scanner.nextInt();

            v[i]=scanner.nextInt();

            n[i]=scanner.nextInt();

        }

        for(int i = 0; i<k; i++) {

            if(n[i]>=0){

                MultiplePack(w[i],v[i],n[i]);//调用多重背包,注意穿参的时候分别是重量，价值和数量

            }else if(n[i]==-1){

                CompletePack(w[i],v[i]);

            }

        }

        System.out.println(dp[money]);

    }

    static void ZeroOnePack(int weight,int value )//01背包是选不选的问题，

    {

        int i;

        for(i = money; i>=weight; i--)

        {

            dp[i] = Math.max(dp[i],dp[i-weight]+value);

        }

    }

    static void CompletePack(int weight,int value)//完全背包是选取多少的问题

    {

        int i;

        for(i = weight; i<=money; i++)

        {

            dp[i] = Math.max(dp[i],dp[i-weight]+value);

        }

    }

    static void MultiplePack(int weight,int value,int number)//多重背包

    {

        if(money<=number*weight)//如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包

        {

            CompletePack(weight,value);

            return ;

        }

        else//否则就将多重背包转化为01背包

        {

            int k = 1;

            while(k<=number)

            {

                ZeroOnePack(k*weight,k*value);

                number = number-k;

                k = 2*k;//这里采用二进制思想

            }

            ZeroOnePack(number*weight,number*value);

        }

    }

}

巴特西

Java实现蓝桥杯算法提高小X的购物计划

试题算法提高小X的购物计划

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法提高 小X的购物计划

试题 算法提高 小X的购物计划

最新文章

热门文章

Java实现蓝桥杯算法提高小X的购物计划

试题算法提高小X的购物计划