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);
        }
    }
}