哼哼哼啊啊啊啊啊……顾冥思彝,就是背包出问题了……(bushi
题目描述
一个人在旅途中的人有一个最多能用M公斤的背包,现在有n件物品,它们的重量分别是W1,W2,...,Wn,它们的价值分别为C1,C2,...,Cn.求此人能获得最大总价值。
Input
第1行:两个整数,M(背包容量,M<=200)和n(物品数量,n<=30);
第2至n+1行:每行两个整数Wi,Ci,表示每个物品的重量和价值。
Output
一个数,表示最大总价值。
样例输入
10 4
2 1
3 3
4 5
7 9
样例输出
12
code:
#include <bits/stdc++.h>
using namespace std;
int n,m,w[901],c[901],f[1501];
int main()
{
cin>>m>>n;
for(int i = 1;i <= n;i++) cin>>w[i]>>c[i];
for (int i = 1;i <= n;i++) for (int j = m;j >= w[i];j--) f[j] = max(f[j], f[j - w[i]] + c[i]);
cout<<f[m];
return 0;
}
标签:...,背包,int,样例,问题,901,模板
From: https://www.cnblogs.com/nasia/p/17520736.html