算法-动态规划（背包）

NO.1 01背包问题

题���：

（）

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

（）

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N  行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 x >> y;for(int i = 1;i > v[i] >> w[i];}int ans = 0;for(int i = 1;i = v[i];j --){dp[j] = max(dp[j],dp[j-v[i]]+w[i]);//ans = max(ans,dp[j]);}}for(int i = 0;i v[i] >> w[i];int ans = 0;for(int i = 1;i > w[i] >> s[i];for(int i = 1;i S;while(k 0){v[cnt] = N * S;w[cnt ++] = W * S;}}for(int i = 0;i = v[i];j --)dp[j] = max(dp[j],dp[j-v[i]] + w[i]); }cout y;for(int i = 1;i > s[i];for(int j = 0;j > v[i][j] >> w[i][j];}for(int i = 1;i = 0;j --)//体积for(int k = 0;k