网站建设专家证书,wordpress写模版,网站后台数据库丢失,wordpress图片预加载个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 原题链接点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 2️⃣题目解析 解法1 状态表示dp[i][j]表示从前i个物品中进行挑选体积不超过j的所有选法中的最大价值。
状态转移方程
dp[i][j] max(dp[i][j],dp[i - 1][j - V[i] * k] k * W[i])
3️⃣解题代码
朴素算法
#includeiostream
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 0;j v;j){for(int k 0;k * V[i] j;k){dp[i][j] max(dp[i][j],dp[i - 1][j - V[i] * k] k * W[i]); }}}cout dp[n][v];return 0;
}时间优化
#includeiostream
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 - 1][j],dp[i][j - V[i]] W[i]);}}cout dp[n][v];return 0;
}空间优化滚动数组
#includeiostream
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[i];j v;j)dp[j] max(dp[j],dp[j - V[i]] W[i]);cout dp[v];return 0;
}
