首页 > 试题广场 >

牛牛与世界杯门票

[编程题]牛牛与世界杯门票

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

今年的世界杯要开始啦，牛牛作为一个球迷，当然不会放过去开幕式现场的机会。但是牛牛一个人去又觉得太过寂寞，便想叫上了他的n个小伙伴陪他一起去莫斯科(一共n+1人)。当牛牛开始订开幕式的门票时，发现门票有m种套餐，每种套餐需要花费x元，包含y张门票，每张门票也可以单独购买，此时这张门票的价格为k元。请问牛牛要怎样选择购买门票，使得他花费的钱最少。(每种套餐可以购买次数没有限制)。

输入描述:

第一行输入三个数字n(0≤n≤999)、m(1≤m≤1000)和k(1≤k≤100000)
接下来m行，每行输入两个数字x_i(1≤xi≤100000)和yi(2≤yi≤1000), 表示套餐的价格和套餐内包含的门票数量。

输出描述:

输出牛牛至少要花费的钱的数量。

示例1

输入

2 2 5
6 2
13 3

输出

算法知识视频讲解

zhangbw_

C++ 完全背包问题

将总人数n + 1当作背包容量，套餐的人数作为每件物品重量
注意可以有余票，如20人可以买30张票(如果这30张票价格更优的话)
最终答案为dp[n + 1]「购买 n + 1张票的最小花费」

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, k, weight[1005], price[1005];
    cin >> n >> m >> k;
    price[0] = k; weight[0] = 1;    // 单人票，价格为k，作为物品0
    for (int i = 1; i <= m; ++i) {    // 添加m种套餐(物品)
        cin >> price[i] >> weight[i];
    }

    int dp[n + 2];    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;    // dp[i]: 购买i张票的最小花费
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n + 1; ++j) {
            if (j >= weight[i]) dp[j] = min(dp[j], dp[j - weight[i]] + price[i]);
            else dp[j] = min(dp[j], price[i]);  // 重点
        }
    }
    cout << dp[n + 1] << endl;
    return 0;
}

编辑于 2022-08-19 22:11:05 回复(0)

JavaScript

w布响丸辣

/*世界杯门票
这个题可以看做是一个背包问题，人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n]即为买到n张票时的最小花费
*/
var line1 = readline().split(' ');
var n = parseInt(line1[0]),
    m = parseInt(line1[1]),
    k = parseInt(line1[2]);
    n++;
var dp = []; 
for(var i=0;i<=n;i++){     dp[i] = i*k;
}

for(var i=0;i<m;i++){
    var line2 = readline().split(' ');
    for(var j=1;j<=n;j++){
        if(j-line2[1]>=0){
            dp[j] = Math.min(dp[j],dp[j-line2[1]]+parseInt(line2[0]));
        }else{
            dp[j] = Math.min(dp[j],parseInt(line2[0]));
        }
    }
}
print(dp[n]);

发表于 2018-09-17 16:20:14 回复(0)

Java

求天求地求Offer

//基本思路：刚开始不整理，就是将买几张票的钱数先存在dp中，等套餐，单买的情况都存好后，
//整理dp[]，整理的话有两种情况：①当前的票数要花的最少的钱数等于小于当前票数的最小钱的情况
//之和（因为小于当前票数的最少的钱已经整理好），②等于大于当前票数花的钱和当前的最小数
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int ticket[]=new int[1001];//表示买i张票所需要的最少的钱
        int m=sc.nextInt();
        int k=sc.nextInt();
        for(int i=0;i<1001;i++){
            ticket[i]=i*k;
        }
        for(int i=0;i<m;i++){
            int mm=sc.nextInt();
            int t=sc.nextInt();
            ticket[t]=Math.min(ticket[t],mm);
        }
        for(int i=1;i<=n+1;i++){
            int min=ticket[i];
            for(int j=1;j<=1000;j++){
                if(j<i)
                    min=Math.min(min,ticket[j]+ticket[i-j]);
                else
                    min=Math.min(min,ticket[j]);
            }
            ticket[i]=min;
        }
        System.out.println(ticket[n+1]);
    }
}

发表于 2018-07-03 22:50:28 回复(0)

桃符

import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s = new Scanner(System.in);
        // 人数数量
        int n = s.nextInt();
        // 套餐数量
        int m = s.nextInt();
        // 单价
        int k = s.nextInt();
        // 定义票的数组
        int[][] tickets = new int[m + 1][2];
        // 遍历获得套餐信息（价钱x，人数y）
        for (int i = 1; i <= m; i++) {
            int x = s.nextInt();
            int y = s.nextInt();
            tickets[i][0] = x;
            tickets[i][1] = y;
        }
        tickets[0][0] = k;
        tickets[0][1] = 1;
        //【套餐】【背包容量（人数）】
        int[][] dp = new int[m+1][n+2];
        for(int i = 1;i<=m;i++){
            dp[i][0] = 0;
        }
        for(int j = 0;j<=n+1;j++){
            dp[0][j] = j* k;
        }
        // 线性规划(套餐->人数)，完全背包，将人数作为容量
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n + 1; j++) {

if(j<tickets[i][1]){//人数<套餐人数

//可能存在套餐价格非常便宜的情况，所以需要将上一种情况与套餐价格进行比较（22元=69人）

                    dp[i][j] = Math.min(dp[i-1][j], tickets[i][0]);
                }else{
                    for(int h = 1;h<=j/tickets[i][1];h++){
                        dp[i][j] = Math.min(dp[i-1][j], dp[i][j-h*tickets[i][1]]+h*tickets[i][0]);
                    }
                }
            }
        }
        System.out.println(dp[m][n+1]);
    }
}

发表于 2018-06-30 13:27:19 回复(1)

昵称已被占用、

写出暴力递归，再改写成动动态规划，未进行任何优化。

/**
 * 
 * 思路：
 *     遍历每种套餐组合，每种套餐均可购买 0 ~ 当前缺少门票/当前套餐提供的票数 （向上取整），最后所得门票大于需求 或者 到达数组尾部 时返回。。
 * 
 * ps：
 *     单买门票等价于票数为1的套餐。
 * 
 * @author Yanjie
 *
 */
public class BuyTicket {

    public static void main(String[] args) throws Exception {

        Scanner in = new Scanner(new FileInputStream("F:\\java\\JavaLearning\\src\\nowcoder\\praticetest\\BuyTicakets.txt"));

        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();

        // 套餐数组，dp[][0]:价格，dp[][1]:票数
        int[][] pacakges = new int[m + 1][2];
        pacakges[0][0] = k;
        pacakges[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            pacakges[i][0] = in.nextInt();
            pacakges[i][1] = in.nextInt();
        }

        System.out.println(process1(pacakges, n, 0, 0));
        System.out.println(process2(pacakges, n));
    }

    /**
     * 暴力递归
     * 
     * @author Yanjie
     *
     * @param pacakges
     * @param n
     * @param curIndex
     * @param curTickets
     * @return
     */
    public static int process1(int[][] pacakges, int n, int curIndex, int curTickets) {

        // base case
        if (curTickets >= n + 1) { // 票数已够
            return 0;
        }
        if (curIndex == pacakges.length) { // 票数未够但已无可用套餐，该方案不满足条件，废弃。
            return -1;
        }

        int minMoney = (n + 1) * pacakges[0][0];

        int curMaxNum = (int) Math.ceil( (double) ((n + 1) - curTickets) / pacakges[curIndex][1] ); // 向上取整，即可以多买票。

        for (int k = 0; k <= curMaxNum; k++) {
            int money = process1(pacakges, n, curIndex + 1, curTickets + k * pacakges[curIndex][1]);
            if (money == -1) {
                continue;
            } else {
                money += pacakges[curIndex][0] * k; // money = 当前套餐花费 + 后续套餐花费
            }
            minMoney = Math.min(minMoney, money);
        }

        return minMoney;

    }

    /**
     * 动态规划
     * 
     * @author Yanjie
     *
     * @param pacakges
     * @param n
     * @return
     */
    public static int process2(int[][] pacakges, int n) {

        // dp
        int[][] dp = new int[pacakges.length + 1][n + 2];

        // base case
        for (int j = 0; j <= n + 1; j++) {
            dp[pacakges.length][j] = -1;
        }

        // 普通位置
        for (int i = pacakges.length - 1; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                int minMoney = (n + 1) * pacakges[0][0];
                int curMaxNum = (int) Math.ceil( (double) ((n + 1) - j) / pacakges[i][1] );
                for (int k = 0; k <= curMaxNum; k++) {
                    int money = 0;
                    if (j + k * pacakges[i][1] <= n + 1) { // 数组越界处理，票数是否够数
                        money = dp[i + 1][j + k * pacakges[i][1]];
                    }
                    if (money == -1) {
                        continue;
                    } else {
                        money += pacakges[i][0] * k;
                    }
                    minMoney = Math.min(minMoney, money);
                }
                dp[i][j] = minMoney;
            }
        }
        return dp[0][0];

    }
}

编辑于 2018-06-27 16:19:48 回复(0)

海超人

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1100;
int dp[maxn][maxn];
int weight[maxn];//存套餐价格
int value[maxn];//存套餐提供票数
int main()
{
int n, m, k;
while (cin >> n)
{
++n;
cin >> m >> k;
memset(dp, 0, sizeof(n));
for (int i = 1; i <= m; ++i)
{
cin >> weight[i] >> value[i];
}
for (int i =1;i<=n;++i )
{
dp[0][i] = i * k;//没人单买不使用套餐的价格。
}
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
{

if (j > value[i])//人数大于套餐中提供票数
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - value[i]] + weight[i]);//不使用当前套餐的价格和使用当前价格的比较
else
{
dp[i][j] = min(dp[i-1][j], weight[i]);//当人数小于等于套餐中提供票数时，分两种情况，①：pass这个套餐。②：使用这个套餐。两者只要比一下最低价就行了
//cout << ans << endl;
}
}

}
cout << dp[m][n] << endl;
}
return 0;
}

编辑于 2018-06-24 19:07:57 回复(0)

勇敢的奋进者123

//动态规划，我更喜欢使用二维数组，更容易理解
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int min(int a, int b)
{
    return (a < b) ? a :b;
}
int main()
{
    int n, m, k;
    int x, y;
    while(cin >> n >> m >> k)
    {
        vector<int> price(m+1);  //price[i]表示第i种方案对应的价格
        vector<int> count(m+1);  //count[i]表示第i中方案对应的人数
        price[0] = k; count[0] = 1; 
        for(int i = 1; i <= m; i++)
        {
            cin >> x >> y;
            price[i] = x;
            count[i] = y;
        }
        //定义dp[i][j]:用前i种方案凑j个人的最少费用
        //最后输出dp[m][n+1]即可
        vector<vector<int> > dp(m+1, vector<int>(n+2, INT_MAX));
        //1.对dp[0][j]:用第0种方法去凑j个人，只能是count[0]的倍数
        for(int j = 0; j <= n+1; j++)
        {
            if(j%count[0] == 0)
                dp[0][j] = (j/count[0])*price[0];
        }
        //2.对dp[i][0]:用前i种方法去凑0个人，即不需要钱，全部置0
        for(int i = 0; i <= m; i++)
            dp[i][0] = 0;
        //3.对dp[i][j]:
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n+1; j++)
            {
                if(j-count[i] >= 0)
                    dp[i][j] = min(dp[i-1][j], dp[i][j-count[i]]+price[i]);
                else
                    dp[i][j] = min(dp[i-1][j], price[i]);
            }
        cout << dp[m][n+1] << endl;
    }
    return 0;
}

发表于 2018-06-28 22:48:04 回复(0)

luckyxue

人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n + 1]即为买到n + 1张票时的最小花费

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int[] dp = new int[n + 2];
            for(int i = 1; i <= n + 1; i++) {
                dp[i] = i * k;
            }
            int x, y = 0;
            while(m-- > 0) {
                x = sc.nextInt();
                y = sc.nextInt();
                for(int i = 1; i <= n + 1; i++) {
                    if(i - y >= 0) {
                        dp[i] = Math.min(dp[i], dp[i - y] + x);
                    } else {
                        dp[i] = Math.min(dp[i], x);
                    }
                }
            }
            System.out.println(dp[n + 1]);
        }
    }
}

发表于 2018-06-30 01:12:31 回复(0)

C/C++

looker.

贪心算法（应该算这个）全部通过，但是感觉有运气成分。每种套餐按人均票价排序，优先选最便宜的套餐买，买到剩余人数小于套餐人数时，考虑下一个稍贵一点套餐，继续搜索，(但此时要考虑特殊情况，即干脆在买一个该套餐，票多就多了，记下这种方式的总钱数sum_[i];)最终价格sum_price；比较常规思路得到的sum_price与各种坑爹情况的sum_[i]的最小值，及最小钱数。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct price
{
    int x;
    int y;
    float x_dy;//平均票价
};
bool compare(price p1, price p2)
{
    return p1.x_dy < p2.x_dy;
}
int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<price>p(m+1);
    price pi;
    for (int i = 0; i < m; i++)
    {

        cin >> pi.x >> pi.y;
        pi.x_dy = float(pi.x) / pi.y;
        p[i] = pi;
    }
    pi.x = k;
    pi.y = 1;
    pi.x_dy = k;
    p[m] = pi;
    sort(p.begin(), p.end(), compare);//按套餐的人均票价排序
    int i = 0;
    int sum_price=0;
    n = n + 1;
    vector<int>sum_;
    //当某种套餐的票数y大于剩余人数时，两种选择
    //    1：再购买一次该套餐
    //    2: 继续选择下一个合适的套餐
    while (n > 0)
    {
        while (n >= p[i].y)
        {
            n = n - p[i].y;
            sum_price += p[i].x;
        }
        sum_.push_back(sum_price + p[i].x);
        i++;
    }
    sum_.push_back(sum_price);
    int min=sum_[0];
    for (auto p : sum_)
    {
        if (min > p)
            min = p;
    }
    cout << min<<endl;
    return 0;
}

发表于 2019-05-25 00:05:06 回复(1)

Freddien

#include <iostream>
#include <algorithm>
using namespace std;
int y_man[1005];
int x_price[1005];
int d[1005];//费用矩阵
 int main()
 {
     int n,m,k;
     cin>> n>> m>>k;
     x_price[0] = k ;y_man[0] = 1;
     for(int i =1 ;i<=m ;i++)
        cin >>x_price[i] >>y_man[i];

     d[0] = 0;
     for(int i = 1;i<=n+1 ;i++)
     {
         d[i] = (n+1)*k; //初始化的d[1-(n+1)]
     }
     for(int i= 0;i<=m;i++) //取前m中方案 求的费用d[j] ;注意 ，一个人单独购票也是一种方案
     {
         for(int j= 1;j<=n+1 ;j++) //更新 费用d[] 矩阵
         {
             if(j >=y_man[i]) 
                 d[j] = min(d[j],d[j-y_man[i]]+x_price[i]);
             else
                 d[j] = min(d[j],x_price[i]);//非常重要，当人数小于团体票时，
             //有可能出现团体票费用比其他组合还便宜
         }
     }
     cout << d[n+1];
     return 0;
 }

发表于 2019-05-16 23:01:23 回复(0)

孙超越a

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n=0,m=0,k=0;

    cin >> n>>m>>k;
    int sun = n + 1; //人数
    int sum1 = 0,sum2=0;
    vector<int> s1;

    int min=sun*k; //全部单买
    int x[1000] = { 0 }, y[1000] = {0};
    for (int i = 0; i < m; i++)
    {
        cin >> x[i] >> y[i]; //输入m行，m中套餐
        //out << endl;
    }
    for (int i = 0; i < m; i++)
    {
        sum1 = ((n + 1) / y[i])*x[i];
        if ((n + 1) % y[i] != 0)
            sum1 = sum1 + x[i]; //全部套餐
        if (sum1 < min)
            min = sum1;
        for (int j = 1; j*y[i] <= n + 1; j++)
        {
            sum2 = j*x[i] + (n + 1 - j*y[i]) * k; //套餐与单买结合
            if (sum2 < min)
                min = sum2;
        }
    }
    cout << min << endl;
    return 0;
}

发表于 2019-05-16 17:21:53 回复(0)

luckydog~~~

#include<iostream>
#include<vector>
long func(std::vector<long> &price,std::vector<std::pair<long,long>> &scheme,long num)
{
if(num<=0)
return 0;
if(price[num]!=0)
return price[num];
std::vector<long> x(scheme.size(),0);
long min_cost=100000*scheme[scheme.size()-1].first;
for(size_t i=0;i<scheme.size();i++)
{
x[i]=func(price,scheme,num-scheme[i].second)+scheme[i].first;
if(min_cost>x[i])
min_cost=x[i];
}
price[num]=min_cost;
return min_cost;
}

int main()
{
long n,m,k,x,y;

std::vector<std::pair<long,long>> scheme;
std::cin>>n>>m>>k;
std::vector<long> price(n+2,0);
while(m>0)
{
m--;
std::cin>>x>>y;
scheme.push_back(std::pair<long,long>(x,y));
}
scheme.push_back(std::pair<long,long>(k,1));
std::cout<<func(price,scheme,n+1);
return 0;
}

发表于 2018-07-04 10:46:39 回复(0)

蛟龙吐火球丰

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int cost;
int k;
bool com(pair<int,int>& a,pair<int,int>&b)
{
    return a.first/a.second>b.first/b.second;
}
void core(vector<pair<int,int>>& co,int idx,int n,int num,int cos,int total)
{
    if(num>=total)
    {
        cost=min(cost,cos);
        return;
    }
    if(cos>cost)
        return;
    cost=min(cos+(total-num)*k,cost);
    for(int i=idx;i<n;i++)  
        core(co,i,n,num+co[i].second,cos+co[i].first,total);

}
int main()
{
    int n,m;
    while(cin>>n>>m>>k)
    {
        vector<pair<int,int>> co(m);
        for(int i=0;i<m;i++)
            cin>>co[i].first>>co[i].second;
        sort(co.begin(),co.end(),com);
        cost=INT_MAX;
        core(co,0,m,0,0,n+1);
        cout<<cost<<endl;
    }
}

发表于 2018-06-30 08:54:13 回复(0)

gengman

//完全背包 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int v[1010],w[1010];
int dp[2100];
int main()
{
    int m,n;
    for(int i=0;i<=2099;i++) dp[i]=inf;
    scanf("%d%d%d",&n,&m,&w[0]);
    v[0]=1;
    n++;
    int maxx=-1;
    dp[0]=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
        if(maxx<v[i]) maxx=v[i];
    }
    for(int i=0;i<=m;i++)
    {
        for(int k=0;k*v[i]<=n+maxx;k++)
        {
            for(int j=k*v[i];j<=n+maxx;j++)
            {
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);

            }
        }
    }
    int minn=inf;
    for(int i=n;i<=n+maxx;i++)
    {
        minn=min(dp[i],minn);
    }
    printf("%d\n",minn);
}

发表于 2018-06-29 19:53:59 回复(0)

Java

刘禅挥泪斩孔明

public class Main { // 动态规划:dp[i]表示i个人的最小花销
  public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), i, j;
    int price, num, dp[] = new int[n+2];// dp[0] == 0
    for (i = 1; i < n+2; ++i)
      dp[i] = k * i;
    for (i = 0; i < m; ++i) {
      price = sc.nextInt();
      num = sc.nextInt();
      for (j = 1; j < n+2; ++j)
        dp[j] = Math.min(dp[j], dp[Math.max(0, j-num)] + price);
    }
    System.out.println(dp[n+1]);
  }
}

编辑于 2018-06-29 12:05:09 回复(0)

Python

翰墨轩lc

n=input();
print n
m=input();
print m
k=input();
print k
x=[];
y=[];
price=[];
for t in range(m):
xi=input();
yi=input();
price1=(n+1)*k;
price2=((n+1)/yi)*xi+(n+1)%2*k;
price
price.append(min(price1,price2))

result=min(price);
print result

发表于 2018-06-28 20:51:42 回复(0)

1367356

// 本题中可能会存在购买某一种套餐之后，人数不够，套餐中有些票是用不着的情况。

//所以买的票数是大于人数的，最多多买多少张票呢。应该为m中套餐中最大票数-1。

// 例如单独一张票 100元，但是有一种套餐是100张票，总共10元钱。其它人都团购完成，还剩余一个人，那么剩余的一个人就应该买这种套餐。所以最后买的票数为n+1+100-1.

//然后用动态规划求解即可。

import java.util.HashMap;

import java.util.*;
import java.util.stream.Collectors;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt(); //n个小伙伴，共n+1个人
int m=scanner.nextInt(); //m中套餐
int k=scanner.nextInt(); //1张门票的价格
int[] arrm = new int[m];

Map<Integer,Integer> map = new HashMap();
for (int i = 0; i < m; i++) { //套餐
int x=scanner.nextInt(); // x 钱数
int y=scanner.nextInt(); //y 人数
arrm[i]=y;
map.computeIfPresent(y,(y1,val)->{
return val>x?x:val;
});
map.putIfAbsent(y, x);
}

OptionalInt max = Arrays.stream(arrm).sorted().max();
int imax = max.getAsInt(); //找到一种张数最多的套餐

int[] arrn = new int[n + 2+imax];

for (int i = 0; i <= n+1+imax; i++) {
arrn[i]=i*k; //第一种，每个人买一张，不买套餐
}

for (int i = 0; i < m; i++) { //m种套餐
int tickNum = arrm[i]; //套餐门票张数
int value = map.get(tickNum); //套餐价格
for (int j = 1; j <= n+1+imax; j++) { //人数
if (j >= tickNum) {
if (arrn[j - tickNum] + value < arrn[j]) {
arrn[j]=arrn[j-tickNum]+value;
}
}
}
}

List<Integer> list = Arrays.stream( arrn ).boxed().collect(Collectors.toList());
List<Integer> list1 = list.subList(n+1 , n+1+imax);
Integer max1 = Collections.min(list1);
System.out.println(max1);
}
}

编辑于 2018-06-27 16:52:49 回复(0)

麦垛上的守望者

改了很久没过：不知道为什么？我自己编的几个测试数据都没问题
那个472是怎么算出来的？
我手动检验了一下，实在凑不出来472，反倒是凑出来了644，就是 22 + 103 + 173*3 ，这三种套餐刚好凑够117张票，结果是644元钱。。。

还有一点就是，我的理解是，不能多买，用套餐凑的话，必须得凑够n+1张

import java.util.Scanner;

public class Main {

long[] dp = new long[n+2]; //当总人数为i时，最少花费
for(int i=0;i=data[j][1]){//
dp[i] = Math.min(dp[i], dp[i-data[j][1]]+data[j][0]);
}
}
}
System.out.println(dp[n+1]);
in.close();
}
}
116 26 450
230 15
531 70
777 63
589 61
266 81
322 77
517 73
820 68
241 77
103 42
256 91
750 87
866 51
569 97
524 83
173 2
22 69
653 14
846 17
896 69
111 90
194 68
326 2
335 18
175 79
933 55

472

你的输出为:

644

借用完全背包的思路，写了另一版，还是出错在这个案例上，同样是472 644

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        int[][] data = new int[m + 1][2];
        for (int i = 1; i < m + 1 && in.hasNextInt(); i++) {
            data[i][0] = in.nextInt();
            data[i][1] = in.nextInt();
        }
        // 单张买也算作一种套餐：花费k，人数1
        data[0][0] = k;
        data[0][1] = 1;
        if (n == 0) {
            System.out.println(k);
            return;
        }

        long[][] dp = new long[m+1][n+2]; // dp[i][j]表示前i个套餐，买j张票的最小花费
        /*for (int i = 0; i < dp.length; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);*/

        for(int i=0;i<dp.length;i++)
            dp[i][0] = 0;
        for(int i=0;i<dp.length;i++)
            dp[i][1] = k;
        for(int i=0;i<=n+1;i++)
            dp[0][i] = k*i;
        for (int i = 1; i <m+1; i++) {
            for (int j = 2; j <=n+1; j++) {
                if (j >= data[i][1]) {//
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-data[i][1]]+data[i][0]);
                }else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[m][n+1]);
        in.close();
    }

编辑于 2018-06-24 12:05:38 回复(12)

WAK

您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为80.00%

测试用例:
116 26 450
230 15
531 70
777 63
589 61
266 81
322 77
517 73
820 68
241 77
103 42
256 91
750 87
866 51
569 97
524 83
173 2
22 69
653 14
846 17
896 69
111 90
194 68
326 2
335 18
175 79
933 55

对应输出应该为:

472

你的输出为:

明明有22元69张票，而且套餐购买无限制，买117张只需要两个22元套餐，结果为什么是472？

发表于 2018-06-23 20:38:03 回复(5)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师数据库工程师信息技术岗区块链动态规划测试开发工程师 2018 2019 大数据开发工程师数据分析师 Java工程师牛客

来自：【2018】牛客模考（...

上传者：小小

难度：

19条回答 61收藏 6108浏览

通过挑战的用户

想被叫靓仔的废话选手

2022-11-17 00:55:14
牛客49959...

2022-09-09 13:42:09
zhangbw_

2022-08-19 22:02:55
空城深处，住着空心、

2022-07-07 13:04:47
祈求顺利毕业

2022-03-31 19:14:57