点菜问题

/*
    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;
}

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

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

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

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

动态规划经典，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;
}

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

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

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

//贪玩递归，你从来没有见过的版本，几要三分钟，你就会爱上这款算法

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

	

求大神看我的代码有什么错误？ 答案错误:您提交的程序没有通过所有的测试用例 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 <algorithm>
#include <iostream>
#include<cstring>
using namespace std;
int dp[1001][101];
int money[101];
int v[101];
int main() {
    int c,n;
    while (scanf("%d %d",&c,&n)!=EOF) {
        for(int i=0;i<n;i++){
            scanf("%d %d",&money[i],&v[i]);
        }
        //没钱时与没有空间时都是问题边界
        for(int x=0;x<=c;x++){
            dp[x][0]=0;
        }
        for(int y=0;y<=n;y++){
            dp[0][y]=0;
        }
        for(int x=1;x<=c;x++){
            for(int y=1;y<=n;y++){
                if(x-money[y-1]<0){//没钱买时直接跳过
                    dp[x][y]=dp[x][y-1];
                }else{//买这个和不买这个哪个评分高
                    dp[x][y]=max(dp[x][y-1],dp[x-money[y-1]][y-1]+v[y-1]);
                }
            }
        }
        printf("%d\n",dp[c][n]);
    }
}
// 64 位输出请用 printf("%lld")

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

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

'''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

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