国外js建设网站,wordpress archives,桑基图在线制作网站,赣州哪里可以做网站算法提高 01背包
时间限制#xff1a;1.0s 内存限制#xff1a;256.0MB 问题描述 给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式 输入的第一行包含两个整数n, m#xff0c;分别表示物品的…
算法提高 01背包
时间限制1.0s 内存限制256.0MB 问题描述 给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式 输入的第一行包含两个整数n, m分别表示物品的个数和背包能装重量。 以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式 输出1行包含一个整数表示最大价值。
样例输入
3 5 2 3 3 5 4 7
样例输出
8
数据规模和约定 1N200,M5000. #includeiostream
#includealgorithm
using namespace std;
int w[210],v[210];
int dp[210][5010];
int ans0;
int main()
{int n,m;cinnm;for(int i1;in;i)cinw[i]v[i];for(int i1;in;i)for(int j0;jm;j){if(jw[i])dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]);else dp[i][j]dp[i-1][j];}coutdp[n][m]endl;
}
空间复杂度还可以进一步优化
#includeiostream
#includealgorithm
using namespace std;
int w[210],v[210];
int dp[5010];
int ans0;
int main()
{int n,m;cinnm;for(int i1;in;i)cinw[i]v[i];for(int i1;in;i)for(int jm;jw[i];j--){dp[j]max(dp[j-w[i]]v[i],dp[j]);}coutdp[m]endl;
}
优化01背包的空间复杂度对解决完全背包问题有一定的意义.
