做娱乐自媒体有哪些网站可以推荐,海口专业网站搭建厂,免费的外网服务器,旅游网站前台怎么做个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 原题链接点击直接跳转到该题目 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述 2️⃣题目解析
状态表示dp[i][j]表示从前i个物品中进行挑选且总价钱不超过j的情况下价格与重要度的乘积的总和的最大值。
状态转移方程
选择第i件物品dp[i][j] dp[i - 1][j]不选择第i件物品前提是j V[i]dp[i][j] dp[i - 1][j - V[i]] V[i] * W[i]
注意可以使用滚动数组进行空间优化填表时需要从右往左进行填表。
3️⃣解题代码
朴素算法
#includeiostream
using namespace std;const int M 26;
const int N 30000;
int dp[M][N],V[M],W[M];int main()
{int n,m;cin n m;for(int i 1;i n;i) cin V[i] W[i];for(int i 1;i m;i){for(int j 1;j n;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]] V[i] * W[i]);}}cout dp[m][n] endl;
}滚动数组进行空间优化代码
#includeiostream
using namespace std;const int M 26;
const int N 30000;
int dp[N],V[M],W[M];int main()
{int n,m;cin n m;for(int i 1;i n;i) cin V[i] W[i];for(int i 1;i m;i){for(int j n;j V[i];j--){dp[j] max(dp[j],dp[j - V[i]] V[i] * W[i]);}}cout dp[n] endl;
}
