华为机试题 ：01 背包

题目描述给定n件物品和一个容量为V的背包。每件物品只能使用一次第i件物品的体积是w[i]价值是v[i]。求解将哪些物品装入背包可使这些物品总体积不超过背包容量且总价值最大。输出最大总价值。输入描述第一行输入两个整数n和V分别表示物品数量和背包容量。接下来n行每行输入两个整数w[i]和v[i]表示第i件物品的体积和价值。输出描述输出最大总价值。示例 1输入text4 5 1 2 2 4 3 4 4 5输出text8说明选择物品 1 和物品 2总体积 3总价值 6选择物品 1、物品 3总体积 4总价值 6最优为选择物品 2 和物品 3总体积 5总价值 8。C 解法cpp#include bits/stdc.h using namespace std; int main() { int n, V; cin n V; vectorint w(n), v(n); for (int i 0; i n; i) { cin w[i] v[i]; } vectorint dp(V 1, 0); for (int i 0; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[V] endl; return 0; }