长春建站网站建设,六安木兰巷,网络营销就是seo正确吗,昆山网站建设书生商友个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 原题链接点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。 2️⃣题目解析
状态表示
dp[i][j] 表示从前i个物品中进行挑选体积不超过j的情况下的最大价值。
状态转移方程
dp[i][j] max(dp[i - 1][j],dp[i - 1][j - v[i] w[i])
注意这里dp[i - 1][j]的情况是一定存在的而dp[i - 1][j - V[i]] W[i]的情况只有在j V[i]时才会存在。
空间优化注意填dp表时需要从右往左填。
3️⃣解题代码
解法1朴素算法二维dp
#includeiostream
#includealgorithm
using namespace std;const int N 1010;
int V[N],W[N],dp[N][N];int main()
{int n,v;cin n v;for(int i 1;i n;i) cin V[i] W[i];for(int i 1;i n;i){for(int j 1;j v;j){dp[i][j] dp[i - 1][j];if(j - V[i] 0) dp[i][j] max(dp[i][j],dp[i - 1][j - V[i]] W[i]);}}cout dp[n][v] endl;return 0;
}解法2滚动数组空间优化
#includeiostream
#includealgorithm
using namespace std;const int N 1010;
int V[N],W[N],dp[N];int main()
{int n,v;cin n v;for(int i 1;i n;i) cin V[i] W[i];for(int i 1;i n;i)for(int j v;j - V[i] 0;j--)dp[j] max(dp[j],dp[j - V[i]] W[i]);cout dp[v] endl;return 0;
}
