茶文化网站设计免费,设计一套网页要多少钱,搜索引擎营销的特点,廊坊网站建设外包问题 J: 【动态规划】简单背包问题II
时间限制: 1 Sec 内存限制: 64 MB 提交: 127 解决: 76 [提交] [状态] [讨论版] [命题人:admin] 题目描述
张琪曼#xff1a;“为什么背包一定要完全装满呢#xff1f;尽可能多装不就行了吗#xff1f;” 李旭琳#xff1a;“你说得…问题 J: 【动态规划】简单背包问题II
时间限制: 1 Sec 内存限制: 64 MB 提交: 127 解决: 76 [提交] [状态] [讨论版] [命题人:admin] 题目描述
张琪曼“为什么背包一定要完全装满呢尽可能多装不就行了吗” 李旭琳“你说得对这和墨老师曾告诉我们的‘日中则昃月满则亏’是一个道理。”所以现在的问题是她们有一个背包容量为v(正整数≤v≤20000)同时有n个魔法石(≤n≤30)每个魔法石有一个体积 (正整数)。要求从n个魔法石中任取若干个装入包内使背包的剩余空间为最小。 输入
第一行为一个整数表示背包容量第二行为一个整数表示有n个魔法石接下来n行分别表示这n个魔法石的各自体积。 输出
只有一个整数表示背包剩余空间。 样例输入
24
6
8
3
12
7
9
7样例输出
0AC代码 #include cstdio#include iostream#include algorithm#include cstringusing namespace std;int n,v;int w[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]]w[i]);return f[v];}int main(){cinvn;for(int i1;in;i)cinw[i];coutv-zeroone()endl;return 0;}
