首页 > 试题广场 >

点菜问题

[编程题]点菜问题
  • 热度指数:12760 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    北大网络实验室经常有活动需要叫外卖,但是每次叫外卖的报销经费的总额最大为C元,有N种菜可以点,经过长时间的点菜,网络实验室对于每种菜i都有一个量化的评价分数(表示这个菜可口程度),为Vi,每种菜的价格为Pi, 问如何选择各种菜,使得在报销额度范围内能使点到的菜的总评价分数最大。     注意:由于需要营养多样化,每种菜只能点一次。

输入描述:
    输入的第一行有两个整数C(1 <= C <= 1000)和N(1 <= N <= 100),C代表总共能够报销的额度,N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间(包括1和100)的的整数,分别表示菜的>价格和菜的评价分数。


输出描述:
    输出只包括一行,这一行只包含一个整数,表示在报销额度范围内,所点的菜得到的最大评价分数。
示例1

输入

90 4
20 25
30 20
40 50
10 18
40 2
25 30
10 8

输出

95
38
/*
    01背包,经典动态规划问题
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int c,n;
int v[maxn],w[maxn];
int f[maxn][maxn];
int main(){
	while(cin>>c>>n){
		for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //input
		for(int i=1;i<=n;i++)
			for(int j=0;j<=c;j++){
				f[i][j] = f[i-1][j];
				if(j>=v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
			}
		cout<<f[n][c]<<endl;
	}
}

// 滚动数组优化成一维的问题
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,c;
int v[maxn],w[maxn];
int f[maxn];
int main(){
    while(cin>>c>>n){
        for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
        for(int i=1;i<=n;i++)
            for(int j=c;j>=v[i];j--)
                f[j] = max(f[j],f[j-v[i]]+w[i]);
        cout<<f[c]<<endl;
    }
    return 0;
}

编辑于 2020-03-24 15:08:34 回复(7)

放在这里引以为戒!!
并不是万物皆可暴力

#include<iostream>
using namespace std;

int c, n;
int v[100], p[100];
int max_val;

void dfs(int idx, int rem_c, int sum_v){
    if(rem_c < 0){
        return;
    }
    if(idx == n || rem_c == 0){
        if(sum_v > max_val){
            max_val = sum_v;
        }
        return;
    }
    dfs(idx + 1, rem_c, sum_v);
    dfs(idx + 1, rem_c - p[idx + 1], sum_v + v[idx + 1]);
}

int main(){
    while(cin >> c >> n){
        max_val = 0;
        fill(v, v + 100, 0);
        fill(p, p + 100, 0);
        for(int i = 0; i < n; i++){
            cin >> p[i] >> v[i];
        }
        dfs(-1, c, 0);
        cout << max_val << endl;
    }
    return 0;
}
发表于 2019-03-14 20:00:07 回复(0)
import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int C = in.nextInt();
            int N = in.nextInt();
            int[][] dp = new int[N+1][C+1];
            int [][] arr = new int[N+1][2];
            for(int i=1;i<=N;i++){
                arr[i][0] = in.nextInt();   //price
                arr[i][1] = in.nextInt();  //score
            }
            for(int i=1;i<=N;i++){
                for(int j=1;j<=C;j++)
                    if(j<arr[i][0])
                        dp[i][j] = dp[i-1][j];
                    else
                        dp[i][j] = Math.max(arr[i][1]+dp[i-1][j-arr[i][0]], dp[i-1][j]);
            }
            System.out.println(dp[N][C]);
        }
    }
}

发表于 2018-03-07 13:14:58 回复(0)
#include<bits/stdc++.h>
using namespace std;
//背包问题
int dp[1001];
int w[1001];
int v[1001];

int main(){
    int c,n;
    while(cin>>c>>n){
        for(int i=0;i<n;i++){
            cin>>w[i]>>v[i];
        }
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<n;i++){
            for(int j=c;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<dp[c]<<endl;
    }
    return 0;
}


发表于 2021-08-30 10:17:58 回复(0)

动态规划经典,0-1背包问题。时间复杂度O(n*m),空间复杂度O(n*m)。注释应该写清楚了

#include<iostream>
#include<algorithm>
using namespace std;
//#define max(a,b) (a>b?a:b)
int main()
{
    int C, N;
    while (cin>>C>>N)
    {
        int* P = new int[N];//价格
        int* V = new int[N];//评价
        for (int i = 0; i < N; i++)
            cin >> P[i] >> V[i];

        //dp数组表示不同容量时获得的最高评价
        int* dp = new int[C + 1];
        //base case
        for (int j = 0; j <= C; j++)
            dp[j] = 0;
        //状态转移:选 点第i个菜/不点第i个菜时,对应评价最高的
        for (int i = 0; i < N; i++)
            for (int j = C; j >= P[i]; j--)//从 什么也没点开始 往 报销资金不够 递推
                dp[j] = max(dp[j], dp[j - P[i]] + V[i]);

        cout << dp[C] << endl;
        delete[] P, V, dp;
    }
    return 0;
}
发表于 2020-07-10 11:31:46 回复(0)
//01背包问题,背包装满的前提下能获得的最大价值
#include<stdio.h>
#define max(a,b) (a>b?a:b)
struct beibao{
    int weight;
    int value;
}num[100];
int main()
{
    int dp[1001],n,t,i,j;//dp[n]即为背包容量n的时候能装下的最大价值
    while(scanf("%d%d",&n,&t)!=EOF)
    {
        for(i=0;i<t;i++)//输入
            scanf("%d%d",&num[i].weight,&num[i].value);
        for(i=0;i<=n;i++)
            dp[i]=0;//初始化每个重量的时候价值都是0;
        for(i=0;i<t;i++)//t种菜
        {
            for(j=n;j>=num[i].weight;j--)//从后向前为了不重复选择菜
                dp[j]=max(dp[j-num[i].weight]+num[i].value,dp[j]);//选择这个菜或者不选这个菜
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

编辑于 2020-04-28 15:23:01 回复(0)
递归算法(太耗时间)
#include<iostream>
#define N 100
using namespace std;
int c,n;
int price[N];
int quality[N];
int max;
int dp(int i,int fare){ //从第i号菜开始点,余下费用为fare
    if(i==n || fare <=0) //没菜点或者没有报销
        return 0;
    if(fare < price[i]) //如果报销金额不够这份菜钱,跳过
        return dp(i+1,fare);
    else{
        int k1 = quality[i]+dp(i+1,fare-price[i]);
        int k2 = dp(i+1,fare);
        if(k1>k2){
			max = k1;
			return k1;
		}
		else{
			max = k2;
			return k2;
		}
    }

}
int main(){
    cin>>c>>n;
    for(int i=0;i<n;i++){
        cin>>price[i]>>quality[i];
    }
    int res = dp(0,c);
	cout<<res;
    return 0;
}

动态规划:
#include<iostream>
#define M 1000
#define N 100
using namespace std;
int dp[N][M];//dp[i][j] 代表恰好花光c-j元的报销费用的当前最大评分值
int p[N]; //菜价
int v[N]; //评分
int c,n;
int main(){
    cin>>c>>n;
    for(int i=0;i<n;i++){
        cin>>p[i]>>v[i];
    }
    for(int j=0;j<=c;j++){
        if(p[0]+j<=c)
            dp[0][j] = v[0];
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<c;j++){
            if(p[i]+j>c) //当前所有报销费用都不够买第i号菜
                dp[i][j]=dp[i-1][j];
            else{
                //cur_v代表买第i号菜时最高评分
                //dp[i-1][j]代表不买i号菜时最高评分
                int k = j+p[i]; 
                int cur_v = v[i] + dp[i-1][k];
                if(cur_v > dp[i-1][j])
                    dp[i][j]=cur_v;
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[n-1][0];
    return 0;
}


发表于 2020-02-20 10:52:57 回复(1)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 101;
const int maxc = 1001;

int p[maxn];        // 价格
int v[maxn];        // 评价分数
int dp[maxc] = {0}; // dp

int main()
{
    int c, n;
    while(cin >> c >> n)
    {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i)
        {
            cin >> p[i] >> v[i];
        }

        for(int i = 1; i <= n; ++i)
        {
            for(int j = c; j >= p[i]; --j)
            {
                dp[j] = dp[j] > dp[j-p[i]]+v[i] ? dp[j] : dp[j-p[i]]+v[i];
            }
        }

        cout << dp[c] << endl;

    }

    return 0;
}


发表于 2016-08-10 09:51:02 回复(0)
DP- 0-1背包问题
注意每种菜只能点一次
#include <stdio.h>
#include <string.h>
int C,N;
int p[105],v[105];  //评价分数.菜的价格
int dp[1005];
int GetMax(int a,int b){
    return (a>b)?a:b;
}
int main(){
    int i,j;
    while(scanf("%d %d",&C,&N)!=EOF){
        for(i=0;i<N;i++)
            scanf("%d %d",&p[i],&v[i]);
        memset(dp,0,sizeof(dp));
        for(i=0;i<N;i++)
            for(j=C;j>=p[i];j--)
                dp[j]=GetMax(dp[j],dp[j-p[i]]+v[i]);
        printf("%d\n",dp[C]);
    }
    return 0;
}

发表于 2019-01-03 09:22:21 回复(3)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
    int C,N;
    while(cin>>C>>N)
    {
        int v,p;
        int f[C+1];
        memset(f,0,sizeof(f));
        for(int i=1;i<=N;i++)
        {
            cin>>v>>p;
            for(int j=C;j>=0;j--)
            {
                if(j>=v)
                    f[j]=max(f[j],f[j-v]+p);
            }
        }
        cout<<f[C]<<endl;
    }
}

发表于 2018-03-25 09:37:14 回复(0)
//贪玩递归,你从来没有见过的版本,几要三分钟,你就会爱上这款算法

#include <iostream>
#include <algorithm>
using namespace std;

int t, m;
int c[101], v[101];
int dp[101][1001];

int rec(int i, int j){
    if (dp[i][j] >= 0)
        return dp[i][j];
    int res;
    if(i == m)
        return 0;
    if (j < c[i])
        res = rec(i + 1, j);
    else
        res = max(rec(i + 1, j), rec(i + 1, j - arr[i]) + v[i]);
    return dp[i][j] = res;
}

int main(){
    while(cin >> t >> m){
        for (int i = 0; i < m; ++i)
            cin >> c[i] >> v[i];
        fill(dp[0], dp[0] + 101 * 1001, -1);
        cout << rec(0, t) << endl;
    }
    return 0;
}
发表于 2019-03-31 21:28:52 回复(1)
求大神看我的代码有什么错误? 答案错误:您提交的程序没有通过所有的测试用例 case通过率为0.00% 测试用例: 635 88 35 7 42 25 88 90 21 7 79 86 38 85 66 85 11 93 60 28 7 37 31 86 38 76 6 58 94 85 76 61 92 98 24 69 26 100 72 63 51 98 93 21 65 38 46 41 58 9 77 36 62 51 1 92 84 28 88 45 75 10 83 31 6 51 8 13 18 66 34 88 59 61 30 92 92 36 43 14 37 2 72 78 43 63 13 46 10 35 68 56 100 33 1 22 75 39 46 33 85 77 23 50 5 7 96 61 74 72 10 30 75 59 26 25 67 39 68 90 97 63 3 31 37 28 72 98 95 77 93 100 66 13 37 39 64 44 63 68 46 38 35 84 47 50 26 80 89 89 15 15 72 100 2 32 83 29 62 3 84 84 93 43 45 92 64 48 7 20 4 65 95 94 35 97 34 61 对应输出应该为: 1927 你的输出为: 1905


#include<stdio.h>
#include<algorithm>
using namespace std;
struct dish{
    int price;
    int score;
    int s;
    bool flag;
    bool operator <(const dish &A)const{
        return s>A.s;
    }
}buf[100];
int main(){
    int c,N;
    while(scanf("%d%d",&c,&N)!=EOF){
        for(int i=0;i<N;i++){
            scanf("%d",&buf[i].price);
            scanf("%d",&buf[i].score);
            buf[i].s=buf[i].score/buf[i].price;
            buf[i].flag=true;
        }
        sort(buf,buf+N);
        int money=0;
        int maxs=0;
        for(int i=0;money<c&&buf[i].flag==true;i++){
            money+=buf[i].price;
            maxs+=buf[i].score;
            buf[i].flag=false;
        }
        printf("%d",maxs);
    }
    return 0;
}
发表于 2018-03-07 20:53:10 回复(1)
while True:
    try:
        c,n=map(int,input().split())
        ***bsp;       for _ in range(n):
            price,value=map(int,input().split())
            v.append(value)
            p.append(price)
        dp=[[0]*(c+1) for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,c+1):
                dp[i][j]=dp[i-1][j]
                if j>=p[i-1]:dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i-1]]+v[i-1])
        print(dp[-1][-1])
    except:
        break
经典dp问题,dp[i][j]表示有i种菜品时,用j元所能实现的最大价值
编辑于 2024-03-28 20:41:22 回复(0)
// // Created by t'r'l on 2024/3/22. // #include <bits/stdc++.h> using namespace std; int dp[101][10001];//dp[i][j]表示前i个菜品,总花费不超过j的评价分数 int main(){ int c,n;  while (scanf("%d%d",&c,&n)!=EOF){ int jiage[n];  int pingfen[n];  for(int i=0;i<n;i++){
            scanf("%d%d",&jiage[i],&pingfen[i]);  } for(int i=0;i<=c;i++){
            dp[0][i]=0;  } for(int i=0;i<=n;i++){
            dp[i][0]=0;  } for(int i=1;i<=n;i++){ for(int j=0;j<=c;j++){
                dp[i][j]=dp[i-1][j];  if (j>=jiage[i-1]){
                    dp[i][j]= max(dp[i][j],dp[i-1][j-jiage[i-1]]+pingfen[i-1]);  }
            }
        }
        printf("%d\n",dp[n][c]);  } return 0; }
发表于 2024-03-22 21:49:35 回复(0)
经典01背包问题
#include <bits/stdc++.h>
using namespace std;

int main() {
    int c,n;
    while(cin >> c >> n) {
        if(c==0 || n==0)
            break;
        // 转化为01背包
        vector<int> prices(n,0);
        vector<int> scores(n,0);

        for(int i=0;i<n;++i) {
            cin >> prices[i] >> scores[i];
        }

        // dp[j]表示容量为j大小的背包最多可以装多大评分的物品
        vector<int> dp(c+1,0);
        for(int i=0;i<n;++i) {
            for(int j=c;j>=prices[i];--j) {
                dp[j] = max(dp[j], dp[j-prices[i]]+scores[i]);
            }
        }

        cout << dp[c] << "\r\n";
    }
    return 0;
}


发表于 2024-03-18 22:44:58 回复(0)
'''0-1背包问题'''

def best(c, p, v, n):
    dp = [0]*(c+1)
    dp[0] = 0
    for i in range(0, n):
        for j in range(c, p[i]-1, -1):
            dp[j] = max(dp[j], dp[j-p[i]] + v[i])
    print(dp[c])

while True:
    try:
        price = []
        vi = []
        c, n = map(int, input().split())
        for i in range(n):
                p, v = map(int, input().split())
                price.append(p)
                vi.append(v)
        best(c, price, vi, n)
    except:
        break

编辑于 2024-03-10 16:00:46 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int dp[1005][1005];
struct cai{
	int price; //价格 
	int weight; //评分相当于重量 
	cai(int price,int weight):price(price),weight(weight){}
};
int main(){
	int c,n; //c表示报销总价,n表示有n种菜 
	while(cin>>c>>n){
		vector <cai> menu;
		int price,weight;
		for(int i=0;i<n;i++){  //获取n个菜的价格和重量 
			cin>>price>>weight;
			menu.push_back(cai(price,weight));
		}
		for(int i=0;i<=n;i++){
			for(int j=0;j<=c;j++){
				if(i==0 ||j==0)  //无菜或者无钱 
					dp[i][j] = 0;
				else{
					price = menu[i-1].price;
					weight = menu[i-1].weight;
					if(j>=price) //菜价小于钱总数 
						dp[i][j] = max(dp[i-1][j],dp[i-1][j-price] + weight);
					else{  //菜价大于钱总数 ,买不到菜 
						dp[i][j]=dp[i-1][j]; 
					}
				}
			}
		}
		cout<<dp[n][c]<<endl;
	}
}

发表于 2024-03-01 16:59:53 回复(0)
蛮简单
#include <iostream>
#include <vector>
using namespace std;

// 每种菜一次
int main() {
int m,n;
while(cin >> m >> n){
vector<int> cost(n+1);
vector<int> value(n+1);
for(int i=1; i <=n;++i){
cin >> cost[i];
cin >> value[i];
}

vector<vector<int>> dp(n+1,vector<int> (m+1,0));
for(int i=1; i <=n;++i){
for(int j=1; j <= m;++j){
// 要这件物品和不要这件物品
if(j >= cost[i]){
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+value[i]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}

cout << dp[n][m] << endl;

}

}

// 64 位输出请用 printf("%lld")

发表于 2023-03-21 22:32:06 回复(0)
//经典0-1背包,采用动态规划的做法
#include "stdio.h"
#include "algorithm"
using namespace std;

int main(){
    int C,N;
    int price[110];
    int credit[110];
    int dp[110][1010];
    while (scanf("%d%d",&C,&N)!=EOF){
        for (int i = 1; i <= N; ++i) {
            scanf("%d%d",price+i,credit+i);
        }
        for (int i = 0; i <= N; ++i) {//i为菜品的下标
            for (int j = 0; j <= C; ++j) {//j为weight(剩下的钱)
                if (i == 0 || j == 0){//没有菜品可选或没钱了
                    dp[i][j] = 0;
                    continue;
                }
                if (j < price[i])
                    dp[i][j] = dp[i-1][j];//菜太贵,超过了weight,没法买
                else
                    dp[i][j] = max(dp[i-1][j-price[i]]+credit[i],dp[i-1][j]);//买此菜品与不买此
                                                                             //菜品中选择评分高的
            }
        }
        printf("%d\n",dp[N][C]);
    }
}
发表于 2023-03-10 11:35:52 回复(0)
#include <stdio.h>
struct goods{
    int price;
    int value;
};
int main(){
    int dp[101][1001] = {0};
    int c, n;
    struct goods a[101];
    scanf("%d%d", &c, &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &a[i].price, &a[i].value);
    }
    for(int i = 1;i <= n; i ++){
        for (int j = 1; j <= c; j ++) {
            int t1 = dp[i-1][j];
            int t2 = 0;
            if (j-a[i].price>=0) {
                t2 = dp[i-1][j-a[i].price]+a[i].value;
            }
            dp[i][j] = t1>t2?t1:t2;
        }
    }
    printf("%d", dp[n][c]);
    return 0;
}

发表于 2023-03-06 15:08:59 回复(0)