外卖满减

[编程题]外卖满减

热度指数：5694 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

你打开了美了么外卖，选择了一家店，你手里有一张满 X 元减 10 元的券，店里总共有 n 种菜，第 i 种菜一份需要 A_i 元，因为你不想吃太多份同一种菜，所以每种菜你最多只能点一份，现在问你最少需要选择多少元的商品才能使用这张券。

数据范围： $1 \le n ，A_i \le 100 \$ , $1 \le X \le 10000 \$

输入描述:

第一行两个正整数n和X，分别表示菜品数量和券的最低使用价格。 接下来一行n个整数，第i个整数表示第i种菜品的价格。

输出描述:

一个数，表示最少需要选择多少元的菜才能使用这张满X元减10元的券，保证有解。

示例1

输入

5 20
18 19 17 6 7

输出

算法知识视频讲解

Java

笔寞

import javax.net.ssl.SSLContext;
import java.lang.management.BufferPoolMXBean;
import java.math.BigInteger;
import java.util.*;
import java.io.*;
import java.util.concurrent.Phaser;
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.ReentrantLock;


/**
   01背包问题的衍生简单扩展版本--- 求得是满足达到固定价值的最小体积  
          直接用01背包的滚动优化版本就好了 时间复杂度 100 * 10000 = 1e6 没啥压力
*/
public class Main {

    static int N = 110, M = 10010, n, m;
    static int[] f = new int[M];
    static int[] nums = new int[N];
    static int res;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); m = in.nextInt();

        for(int i = 0; i < n; i ++){
            int x = in.nextInt();
            for(int j = M - 1; j >= x; j --)
                f[j] = Math.max(f[j], f[j - x] + x);  // 01背包模板
        }
        
        for(int i = m; i < M; i ++){  //求可以大于m的最小体积
            if(f[i] >= m){
                res = i;
                break;
            }
        }
        System.out.println(res);
    }

}

发表于 2021-07-29 21:27:20 回复(0)

Java

何止hz

//0-1背包问题
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-11 12:25
 * @Description: 外卖满减
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = br.readLine().split(" ");
        int n = Integer.valueOf(line1[0]);
        int X = Integer.valueOf(line1[1]);
        String[] line2 = br.readLine().split(" ");
        int A[] = new int[n];
        int total = 0;
        for (int i = 0; i < n; i++){
            A[i] = Integer.valueOf(line2[i]);
            total += A[i];
        }
        int w = total - X;
        int dp[][] = new int[n+1][w+1];
        for (int i = 1; i <=n; i++)
            for (int j = 1; j <= w; j++){
                dp[i][j] = dp[i-1][j];
                if (j >= A[i-1])
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-A[i-1]] + A[i-1]);
            }
        System.out.println(total - dp[n][w]);
    }
}

发表于 2020-05-11 12:39:35 回复(0)