首页 > 试题广场 >

黄金瞳

[编程题]黄金瞳
  • 热度指数：749 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小庄在一次机缘巧合的机会，眼睛获取了黄金瞳，黄金瞳的功能是可以看到m种物品10天以后的价格。但是这些物品属于限购物资，最多只能购买一定的数量。现在小庄有资金x可以投资这些物品，如何操作才能实现10天后资产价值最大。

输入描述:
第一行 当前资金 x
第二行物品种类m
第三行每种物品限购数量，m个数字
第四行物品当前价格，m个数字
第五行物品10天后价格，m个数字


输出描述:
10天后资产价值最大值
示例1

输入

11
2
6 5
3 2
5 3

输出

18

说明

第一种物品买3个，第二种物品买1个，初期资产3*3+2*1=11，10天后资产价值最大5*3+3*1=18
算法知识视频讲解
添加回答
飞翔的鱼123头像 飞翔的鱼123
知道为什么没有js的提交答案吗，因为这个测试用例空格，真的操蛋，看了两个小时检查错误
发表于 2022-07-11 22:09:21 回复(0)
pein531头像 pein531
这个题思路并不难，从左往右进行暴力递归的尝试，写出递归逻辑后就可以改成记忆化搜索或者动态规划。但是我怀疑本题的测试用例是有问题的，下面进行列举
case 1：
29
3
8 4 9
3 6 4
30 58 128
预期输出897，注意到30,58和128都是偶数，它们的整数倍组合起来怎么可能得到一个奇数？

case 2：
50
1
3
13
24
预期输出83，和上面一样，偶数的倍数不可能得到个奇数。同时，83根本不能被24整除，怎么可能得到83？

case 3：
10
4
1 1 1 1
6 4 5 3
6 5 7 5
预期输出14，每个物品最多只能选择一个，谁能告诉我怎么得到14？6,5,7,5只有两个7能得到14吧，但每个物品限购1个，这答案到底是怎么算出来的？

还有一个case由于数据量比较大，不能一眼看出问题，这里就不列出来了，但凭这三个case我有理由怀疑那个case也是错的
下面给出一个记忆化搜索的代码，以上提到的4个case过不了，但是我感觉思路是没有问题的，欢迎大佬指正。 
import java.util.Scanner;
import java.util.Arrays;

class Item {
    public int limit;
    public int cur;
    public int future;
    public Item(int limit){
        this.limit = limit;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int m = sc.nextInt();
        Item[] items = new Item[m];
        for(int i = 0; i < m; i++){
            items[i] = new Item(sc.nextInt());
        }
        for(int i = 0; i < m; i++){
            items[i].cur = sc.nextInt();
        }
        for(int i = 0; i < m; i++){
            items[i].future = sc.nextInt();
        }
        int[][] dp = new int[m][x + 1];
        System.out.println(Math.max(x, dfs(items, 0, x, dp)));
    }
    
    private static int dfs(Item[] items, int index, int rest, int[][] dp) {
        if(index == items.length || rest < items[index].cur){
            // 钱不够或物品到头了，后面都无法再产生收益
            return 0;
        }
        if(dp[index][rest] > 0){
            return dp[index][rest];
        }
        // 不选当前物品
        int p1 = dfs(items, index + 1, rest, dp);
        // 选当前物品
        int p2 = 0;
        for(int nums = 0; nums <= items[index].limit && nums * items[index].cur <= rest; nums++){
            p2 = Math.max(p2, nums * items[index].future + dfs(items, index + 1, rest - nums * items[index].cur, dp));
        }
        dp[index][rest] = Math.max(p1, p2);
        return dp[index][rest];
    }
}
根据记忆化搜索可以改出动态规划，其实就是个背包问题 
import java.util.Scanner;
import java.util.Arrays;

class Item {
    public int limit;
    public int cur;
    public int future;
    public Item(int limit){
        this.limit = limit;
    }
}

public class Main {
    static int maxProfit = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int m = sc.nextInt();
        Item[] items = new Item[m];
        for(int i = 0; i < m; i++){
            items[i] = new Item(sc.nextInt());
        }
        for(int i = 0; i < m; i++){
            items[i].cur = sc.nextInt();
        }
        for(int i = 0; i < m; i++){
            items[i].future = sc.nextInt();
        }
        int[] dp = new int[x + 1];
        for(int index = 0; index < m; index++){
            for(int rest = x; rest >= items[index].cur; rest--){
                int p = 0;
                for(int nums = 0; nums <= items[index].limit && nums * items[index].cur <= rest; nums++){
                    p = Math.max(p, rest + nums * items[index].future + dp[rest - nums * items[index].cur]);
                }
                dp[rest] = Math.max(dp[rest], p);
            }
        }
        System.out.println(dp[x]);
    }
}
===========================分割线=============================
根据评论区同学的指正，发现是要加上买完物品之后剩余的资金，所以记忆化搜索第35行是要返回rest，而不是0。 
import java.util.Scanner;
import java.util.Arrays;

class Item {
    public int limit;
    public int cur;
    public int future;
    public Item(int limit){
        this.limit = limit;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int m = sc.nextInt();
        Item[] items = new Item[m];
        for(int i = 0; i < m; i++){
            items[i] = new Item(sc.nextInt());
        }
        for(int i = 0; i < m; i++){
            items[i].cur = sc.nextInt();
        }
        for(int i = 0; i < m; i++){
            items[i].future = sc.nextInt();
        }
        int[][] dp = new int[m][x + 1];
        System.out.println(Math.max(x, dfs(items, 0, x, dp)));
    }
    
    private static int dfs(Item[] items, int index, int rest, int[][] dp) {
        if(index == items.length || rest < items[index].cur){
            // 钱不够或物品到头了，后面都无法再产生收益，直接返回剩下的钱
            return rest;
        }
        if(dp[index][rest] > 0){
            return dp[index][rest];
        }
        // 不选当前物品
        int p1 = dfs(items, index + 1, rest, dp);
        // 选当前物品
        int p2 = 0;
        for(int nums = 0; nums <= items[index].limit && nums * items[index].cur <= rest; nums++){
            p2 = Math.max(p2, nums * items[index].future + dfs(items, index + 1, rest - nums * items[index].cur, dp));
        }
        dp[index][rest] = Math.max(p1, p2);
        return dp[index][rest];
    }
}
动态规划也要做出相应的修改，这里就不写了
编辑于 2022-03-07 17:15:18 回复(3)
牛客86598729号头像 牛客86598729号
回溯 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int m = sc.nextInt();
        // products[i][0]:限购数量，products[i][1]:当前价格，products[i][2]:10天后价格
        int[][] products = new int[m][3];
        for (int j = 0; j < 3; j++) {
            for (int i = 0; i < m; i++) {
                products[i][j] = sc.nextInt();
            }
        }

        System.out.println(maxProfit(x, products));
    }
    
    private static int maxProfit(int x, int[][] products) {
        // 根据单位价格可获取的利润排序，如：现在3元，10天后5元，单位价格的利润为（5-3）/3
        Arrays.sort(products, (a, b) -> (b[2] - b[1]) * a[1] - (a[2] - a[1]) *b[1]);
        // 下标索引代表未花的钱，mem[i]代表此时的能够拥有的最大资金
                int[] mem = new int[x + 1];
        mem[x] = x;    // 一个商品都不买时，最大资金即为原有资金
        
        // recursion with memorization
        backtrack(x, products, mem);

        int ans = x;
        for (int item : mem) {
            ans = Math.max(ans, item);
        }
        return ans;
    }

    private static void backtrack(int remX, int[][] products, int[] mem) {
        for (int[] product : products) {
            // 有利润 && 仍可购买 && mem[remX - product[1]]未更新过
            // 排序过的数组保证第一次存储的mem[i]即为最优
            if (product[1] < product[2] && product[0] > 0 && remX - product[1] >= 0 && mem[remX - product[1]] == 0) {
                product[0]--;
                mem[remX - product[1]] = mem[remX] + product[2] - product[1];
                backtrack(remX - product[1], products, mem);
                product[0]++;
            }
        }
    }
}


编辑于 2022-09-08 15:19:07 回复(0)
ecjtu20-计算机科学与技术-卢威头像 ecjtu20-计算机科学与技术-卢威 
#include<iostream>
#include<vector>
using namespace std;

int main() {
    int bagSize;
    cin>>bagSize;
    int num;
    cin>>num;
    vector<int> nums(num);
    for (int i = 0; i < num; ++i) {
        cin>>nums[i];
    }
    vector<int> weights(num);
    for (int i = 0; i < num; ++i) {
        cin>>weights[i];
    }
    vector<int> values(num);
    for (int i = 0; i < num; ++i) {
        cin>>values[i];
    }
    for (int i = 0; i < num; ++i) {
        int count = nums[i];
        while (count > 1) {
            weights.emplace_back(weights[i]);
            values.emplace_back(values[i]);
            --count;
        }
    }
    vector<int> dp(bagSize + 1, 0);
    for (int i = 0; i < weights.size(); ++i) {
        for (int j = bagSize; j >= weights[i]; --j) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
//    for (auto& w : weights) cout << w << ' ';
//    cout << endl;
//    for (auto& v : values) cout << v << ' ';
//    cout << endl;
    int i = bagSize;
    while (i > 0 && dp[i] == dp[i - 1]) {
        --i;
    }
    int res = dp[i] + bagSize - i;
    cout << res << endl;
    return 0;
}
转化为0-1背包问题，考虑到一个情况是，如果背包装不满，就是钱没用完的话，总收益等与10天后的收益+之前剩余的钱
发表于 2022-05-27 19:55:58 回复(2)
lyiopue头像 lyiopue
背包问题，不过要注意审题，求得是10天后的资产最大，这里的资产包括买的物品的总价值和剩下的钱。因此动态规划数组初始化时当没买物品时，值为i(i是0到m)。
发表于 2022-03-05 11:53:36 回复(0)
别的不会就会做题头像 别的不会就会做题
评论有人说可以转化成0-1 knapsack，对于数量比较多这就不一定很好了，因为可能占很大内存 
import java.util.*;

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int m = scanner.nextInt();
        int[] lim = new int[m];
        int[] a = new int[m];
        int[] b = new int[m];
        for (int i = 0; i < m; i++)
            lim[i] = scanner.nextInt();
        for (int i = 0; i < m; i++)
            a[i] = scanner.nextInt();
        for (int i = 0; i < m; i++)
            b[i] = scanner.nextInt();
        int[][] dp = new int[m + 1][x + 1];
        for (int j = 0; j <= x; j++)
            dp[0][j] = j;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= x; j++)
                for (int k = 0; k <= Math.min(lim[i - 1], j / a[i - 1]); k++)
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * a[i - 1]] + k * b[i - 1]);
        System.out.println(dp[m][x]);
    }
}


发表于 2025-01-28 19:22:09 回复(0)
C/C++
双料特工头像 双料特工
01背包问题，把不同种物品按最多个数摊开，变成单个物品，物品现价格看成质量，以后价格看成价值。考虑剩余钱数，所以要在dp表上逆向查找，找到现价值最高时花了多少钱，于是得到剩了多少钱。
#include<bits/stdc++.h>
using namespace std;
struct good
{
    int limit=0;
    int nowv=0;
    int willv=0;
};
int main()
{
    int money,m,count=0;
    cin>>money;
    cin>>m;
    good g[m];
    for(int i=0;i<m;i++)
    {
        cin>>g[i].limit;
        count+=g[i].limit;
    }
    good gg[count];
    int k=0;
    for(int i=0;i<m;i++)
    {
        cin>>g[i].nowv;
        for(int j=k;j<k+g[i].limit;j++)
        {
            gg[j].nowv=g[i].nowv;
        }
        k=k+g[i].limit;
    }
    k=0;
    for(int i=0;i<m;i++)
    {
        cin>>g[i].willv;
        for(int j=k;j<k+g[i].limit;j++)
        {
            gg[j].willv=g[i].willv;
        }
        k=k+g[i].limit;
    }
    int dp[money+1];
    for(int i=0;i<=money;i++)
        dp[i]=0;
    for(int i=0;i<count;i++)
    {
        for(int j=money;j>=gg[i].nowv;j--)
        {
            dp[j]=max(dp[j],dp[j-gg[i].nowv]+gg[i].willv);
        }
    }
    int i=money;
    while(i>0&&dp[i]==dp[i-1])
    {
        i--;
    }
    cout<<dp[money]+money-i;
    return 0;
}
发表于 2022-09-14 21:20:48 回复(0)
wpn头像 wpn 
my_money = int(input().strip())
class_num = int(input().strip())
num_class = list(map(int, input().strip().split()))
price_now = list(map(int, input().strip().split()))
price_after = list(map(int, input().strip().split()))
price_make = []
for i in range(len(price_now)):
    price_make.append(price_after[i] - price_now[i])
now_price = []
make_price = []
for i in range(class_num):
    for j in range(num_class[i]):
        now_price.append(price_now[i])
        make_price.append(price_make[i])
dp = [[0 for i in range(my_money+1)] for i in range(len(now_price))]
for j in range(1, my_money+1):
    if j >= now_price[0]:
        dp[0][j] = make_price[0]
for i in range(len(now_price)):
    for j in range(1, my_money+1):
        if now_price[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - now_price[i]] + make_price[i])
print(my_money+dp[-1][-1])

发表于 2022-08-25 10:26:45 回复(0)
offer砸我、头像 offer砸我、

多重背包问题，展开为0-1背包问题

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func main() {

    atoi := func(x []string) []int {
        t := []int{}
        for _, val := range x {
            if val==""{
                continue
            }
            tmp, _ := strconv.Atoi(val)
            t = append(t, tmp)
        }
        return t
    }
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    x, _ := strconv.Atoi(scanner.Text())
    scanner.Scan()
    m, _ := strconv.Atoi(scanner.Text())
    scanner.Scan()
    xg := atoi(strings.Split(scanner.Text(), " "))
    scanner.Scan()
    curPrice := atoi(strings.Split(scanner.Text(), " "))
    scanner.Scan()
    futurePrice := atoi(strings.Split(scanner.Text(), " "))

    ans := MySolution(x, m, xg, curPrice, futurePrice)
    fmt.Println(ans)
}

func MySolution(x, m int, xg []int, curPrice []int, futurePrice []int) int {
    // 本题是多重背包问题
    // 将多重背包问题展开为0-1背包问题
    for i := 0; i < m; i++ {
        count := xg[i]
        for count > 1 {
            curPrice = append(curPrice, curPrice[i])
            futurePrice = append(futurePrice, futurePrice[i])
            count--
        }
    }
    max := func(a, b int) int {
        if a > b {
            return a
        }
        return b
    }

    dp := make([]int, x+1) //0-x的下标，表示背包的容量从0-x
    for i := 0; i < len(curPrice); i++ {
        // 逆序为0-1，正序为完全背包
        for j := x; j >= curPrice[i]; j-- {
            dp[j] = max(dp[j], dp[j-curPrice[i]]+futurePrice[i])
        }
    }
    i:=x
    for i>0&&dp[i]==dp[i-1]{
        i-- //获取用掉的钱
    }
    return (dp[i]+x-i)
}
发表于 2022-08-24 22:48:22 回复(0)
牛客801007301号头像 牛客801007301号
发表于 2022-04-09 16:45:26 回复(2)
躺平66头像 躺平66
有没有大佬解释一下？
发表于 2022-02-28 01:18:34 回复(1)
提交观点

问题信息

上传者：小小
难度：
11条回答 1518浏览

热门推荐

通过挑战的用户

相关试题

黄金瞳

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号