首页 > 代码库 > hdu2602 Bone Collector (01背包)
hdu2602 Bone Collector (01背包)
本文出自:http://blog.csdn.net/svitter
题意:典型到不能再典型的01背包。给了我一遍AC的快感。
//============================================================================ // Name : 2602.cpp // Author : vit // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define max(a, b) a > b ? a : b struct Bone{ int val; int vol; }; Bone b[1010]; int dp[1010]; void ace(){ //work point int t; int i, j ,k; //num int n, v; cin >> t; while(t --){ memset(dp, 0, sizeof(dp)); scanf("%d%d", &n, &v); for(i = 0; i < n; i++){ scanf("%d", &b[i].val); } for(i = 0; i < n; i++){ scanf("%d", &b[i].vol); } for(i = 0; i < n; i++) for(j = v; j >= b[i].vol; j--){ dp[j] = max(dp[j], dp[j - b[i].vol] + b[i].val); } printf("%d\n", dp[v]); } } int main() { ace(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。