DP|[DP] 完全背包问题 HUSTOJ2820
题目描述 设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M,而价值的和为最大。
输入 【DP|[DP] 完全背包问题 HUSTOJ2820】第一行:两个整数,M(背包容量,M≤200)和N(物品数量,N≤30);
第2..N+1行:每行二个整数Wi,Ci,表示每个物品的重量和价值。
输出 仅一行,一个数,表示最大总价值。
样例输入
10 4 2 1 3 3 4 5 7 9
样例输出
max=12
#include using namespace std;
int main()
{
int m,n;
while(cin>>m>>n)
{
int w[31],c[31];
for(int i=0;
i>w[i]>>c[i];
int dp[31][201];
memset(dp,0,sizeof(dp));
for(int i=0;
ij) dp[i+1][j]=dp[i][j];
else
{
dp[i+1][j]=
max(dp[i][j],dp[i+1][j-w[i]]+c[i]);
}
}
cout<<"max="<
推荐阅读
- parallels|parallels desktop 解决网络初始化失败问题
- jhipster|jhipster 升级无效问题
- “精神病患者”的角度问题
- 解决SpringBoot引用别的模块无法注入的问题
- Hive常见问题汇总
- 姚老师互动问答会|姚老师互动问答会 # 问题001(如何更有智慧的和身边人分享金刚智慧())
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 【教育故事】|【教育故事】 一个“问题学生”的蜕变
- 别墅庭院设计,不同的别墅庭院设计也给人视觉上完全不一样的!
- 蓝桥杯试题