现在的网站前端用什么做,oa系统官网,盐城网站建设电话,网页设计专业公司文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】 AC代码 题目
【题目描述】
一个旅行者有一个最多能装 M M M 公斤的背包#xff0c;现在有 n n n 件物品#xff0c;它们的重量分别是 W 1 #xff0c; W 2 #xff0c; . . . , W n W_1#xff0c… 文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】 AC代码 题目
【题目描述】
一个旅行者有一个最多能装 M M M 公斤的背包现在有 n n n 件物品它们的重量分别是 W 1 W 2 . . . , W n W_1W_2...,W_n W1W2...,Wn,它们的价值分别为 C 1 , C 2 , . . . , C n C_1,C_2,...,C_n C1,C2,...,Cn求旅行者能获得最大总价值。
【输入】
第一行两个整数 M M M(背包容量 M 200 M200 M200)和N(物品数量 N 30 N30 N30)
第 2.. N 1 2..N1 2..N1行每行二个整数 W i C i W_iC_i WiCi表示每个物品的重量和价值。
【输出】
仅一行一个数表示最大总价值。
【输入样例】
10 4
2 1
3 3
4 5
7 9【输出样例】
12AC代码
#include bits/stdc.h
using namespace std;
int v[1145],w[1145],dp[1145][1145],m,n,i,j;
int main() {cinmn;for(i1;in;i) {cinw[i]v[i];}for(i1;in;i) {for(j1;jm;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]);}} }coutdp[n][m];return 0;
}
