题目
【题目描述】
一个旅行者有一个最多能装 M M M 公斤的背包，现在有 n n n 件物品，它们的重量分别是 W 1 ， W 2 ， . . . , W n W_1，W_2，...,W_n W1，W2，...,Wn,它们的价值分别为 C 1 , C 2 , . . . , C n C_1,C_2,...,C_n C1,C2,...,Cn，求旅行者能获得最大总价值。
【输入】
第一行：两个整数， M M M(背包容量， M < = 200 M<=200 M<=200)和N(物品数量， N < = 30 N<=30 N<=30)；
第 2.. N + 1 2..N+1 2..N+1行：每行二个整数 W i ， C i W_i，C_i Wi，Ci，表示每个物品的重量和价值。文章来源：https://www.toymoban.com/news/detail-642331.html
【输出】
仅一行，一个数，表示最大总价值。文章来源地址https://www.toymoban.com/news/detail-642331.html
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
AC代码
#include <bits/stdc++.h>
using namespace std;
int v[1145],w[1145],dp[1145][1145],m,n,i,j;
int main() {
cin>>m>>n;
for(i=1;i<=n;i++) {
cin>>w[i]>>v[i];
}
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) {
if(w[i]>j) {
dp[i][j]=dp[i-1][j];
}
else {
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
到了这里，关于信息学奥赛一本通——1267：【例9.11】01背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
