做空机构的网站,龙海建设局网站,wordpress多媒体分类,贵州快速整站优化描述
给定n种物品和一个背包#xff0c;物品i的重量是Wi#xff0c;其价值为Vi#xff0c;问如何选择装入背包的物品#xff0c;使得装入背包的物品的总价值最大#xff1f;
在选择装入背包的物品时#xff0c;对每种物品i只能有两种选择#xff0c;装入或者不装入…描述
给定n种物品和一个背包物品i的重量是Wi其价值为Vi问如何选择装入背包的物品使得装入背包的物品的总价值最大
在选择装入背包的物品时对每种物品i只能有两种选择装入或者不装入不能装入多次也不能部分装入。
输入描述
第一行输入物品的个数n。
第二行输入物品的重量序列w。(中间有空格
第三行输入物品的价值序列v。中间有空格
第四行输入背包容量c。
输出描述
第一行输出装入背包的物品。用0和1表示中间无空格
第二行输出最大价值。
用例输入 1
3
3 4 5
4 5 6
10
用例输出 1
011
11
提示:
n100; 1Wi,Vi100;
本题是典型的背包问题唯一的难点就是如何查询背包元素。
思路
利用逆推发反向查找如果本像元素与上一列元素一样则没装否则装了由此可推出以下代码 string ans;int Wc;for (int in;n0 s0;i--){if (sdp[i-1][W]) ans0ans;else{ans1ans;s-v[i-1];W-w[i-1];}}
则利用动态规划将代码完善
#includebits/stdc.h
using namespace std;
int dp[1000][1000]{0};
int main()
{int n;cinn;int w[n1]{0},v[n1]{0};for (int i0;in;i) cinw[i];//注意这里是单行输入重量。for (int i0;in;i) cinv[i];//单行输入价值。int c;cinc; for (int i1;in;i){for (int j1;jc;j){if (w[i-1]j) dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i-1]]v[i-1]);//动态规划else (dp[i][j]dp[i-1][j]);}}int sdp[n][c];//开始逆推string ans;int Wc;for (int in;n0 s0;i--){if (sdp[i-1][W]) ans0ans;else{ans1ans;s-v[i-1];W-w[i-1];}}int kn-ans.size();while (k--) ans0ans;//处理一下coutansendldp[n][c];//输出
}
