输入的第一行有两个整数C(1 <= C <= 1000)和N(1 <= N <= 100),C代表总共能够报销的额度,N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间(包括1和100)的的整数,分别表示菜的>价格和菜的评价分数。
输出只包括一行,这一行只包含一个整数,表示在报销额度范围内,所点的菜得到的最大评价分数。
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; }
放在这里引以为戒!!
并不是万物皆可暴力
#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; }
#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> #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; }
#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
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元所能实现的最大价值
// // 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; }
#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; }
'''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; } }
#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; }