网站页面制作软件,工信部的网站备案信息,网络软件,如何提高网站访问量问题 H: 【动态规划】0/1背包问题
时间限制: 1 Sec 内存限制: 64 MB 提交: 152 解决: 95 [提交] [状态] [讨论版] [命题人:admin] 题目描述
张琪曼和李旭琳有一个最多能用m公斤的背包#xff0c;有n块魔法石#xff0c;它们的重量分别是W1#xff0c;W2#xff0c;…有n块魔法石它们的重量分别是W1W2…Wn它们的价值分别为C1C2…Cn。若每种魔法石只有一件问能装入的最大总价值。 输入
第一行为两整数m和n以下n行中每行两个整数WiCi分别代表第i件物品的重量和价值。 输出
输出一整数即最大价值。 样例输入
8 3
2 3
5 4
5 5样例输出
8AC代码
#include cstdio#include iostream#include cstring#include algorithmusing namespace std;int n,v;int w[100100],c[100100];int f[100100];int zeroone(){for(int i1;in;i)for(int jv;jw[i];j--)f[j]max(f[j],f[j-w[i]]c[i]);return f[v];}int main(){cinvn;for(int i1;in;i)cinw[i]c[i];coutzeroone()endl;return 0;}
