【问题描述】
八戒在魔法森林游玩时,不慎迷路,沿着小溪路走下去,不知不觉来到一个洞口前。八戒壮着胆子进入洞中,走了几十步,竟豁然开朗。原来洞中深处是无尽的宝藏,八戒立刻来了精神,准备占为己有。可是八戒背包容量有限,最多可装入m千克的物品。八戒仙术不精,只能对部分宝物的价值与分量完成预估,预估后八戒获得了每一件宝物的重量w与价值c,请你来计算一下,八戒的背包最多能放入价值多少的宝物呢?
输入:第一行两个整数,分别为背包的最大容量m以及可以估计的宝物数量n接下来n行每行两个整数分别为宝物的重量w与其价值c( 0<m,n<100)。
输出:一个整数,表示m大的背包最多可容纳的宝物价值总和。重量w与价值C各不相同,请你来计算一下,八戒的背包最多能放入价值多少的宝石呢?
【样例输入】
8 3
2 3
5 4
5 5
【样例输出】
8
#include<iostream> using namespace std; int f[101], weight[101], value[101]; int main(){ int m, n; cin>>m>>n; for(int i=1; i<=n; i++) cin>>weight[i]>>value[i]; for(int i=1; i<=n; i++){ for(int j=m; j>=0; j--){ if(j>=weight[i]){ // 动态转移方程 f[j]=max(f[j],value[i]+f[j-weight[i]]); } } } cout<<f[m]; return 0; }
标签:背包,weight,int,宝物,八戒,101,优化 From: https://www.cnblogs.com/dks0313/p/16589766.html