首页 > 代码库 > 南阳311
南阳311
1 //完全背包,可通过另一数组存重量的最大价值进行优化 2 #include<iostream> 3 #define inf 1<<29 4 using namespace std; 5 int Room; 6 int bag[50005]; 7 8 void init(int n) 9 { 10 bag[0] = 0; 11 for(int i=1; i<=n; ++i) 12 bag[i] = -inf; 13 } 14 15 void complete_bag(int r,int v) 16 { 17 for(int i=r; i<=Room; ++i) 18 if(bag[i-r]+v > bag[i]) 19 bag[i] = bag[i-r] + v; 20 } 21 22 int main() 23 { 24 int n,num,room,val; 25 cin >> n; 26 while(n--) 27 { 28 cin >> num >> Room; 29 init(Room); 30 while(num--) 31 { 32 cin >> room >> val; 33 complete_bag(room,val); 34 } 35 if(bag[Room] > 0) 36 cout << bag[Room] << endl; 37 else 38 cout << "NO" << endl; 39 } 40 return 0; 41 }
南阳311
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。