吴镇宇做的电影教学网站,温岭手机网站建设,小程序开发工具编辑器,开网站做代发某工厂预计明年有A、B、C、D四个新建项目#xff0c;每个项目的投资额Wk及其投资后的收益Vk如下表所示#xff0c;投资总额为30万元#xff0c;如何选择项目才能使总收益最大#xff1f; Project Wk Vk A 15 12 B 10 8 C 12 9 D 8 5
声明一个 二维数组
m[…某工厂预计明年有A、B、C、D四个新建项目每个项目的投资额Wk及其投资后的收益Vk如下表所示投资总额为30万元如何选择项目才能使总收益最大 Project Wk Vk A 15 12 B 10 8 C 12 9 D 8 5
声明一个 二维数组
m[ i ][ j ] 表示 在面对第 i 件物品且背包容量为 j 时所能获得的最大价值
j w[i]
这时候背包容量不足以放下第 i 件物品只能选择不拿 m[ i ][ j ] m[ i-1 ][ j ]
jw[i]
这时背包容量可以放下第 i 件物品我们就要考虑拿这件物品是否能获取更大的价值。
如果拿取
m[ i ][ j ]m[ i-1 ][ j-w[ i ] ] v[ i ] 这里的m[ i-1 ][ j-w[ i ] ]指的就是考虑了i-1件物品背包容量为j-w[i]时的最大价值也是相当于为第i件物品腾出了w[i]的空间。
如果不拿
m[ i ][ j ] m[ i-1 ][ j ] for (int i 1; i n; i){for (int j 1; j c; j){if (j w[i])m[i][j] max(m[i - 1][j], m[i - 1][j - w[i]] v[i]);elsem[i][j] m[i - 1][j];}}
完整代码
#include iostream
#include cstring
#include algorithmusing namespace std;int main()
{int v[7] { 0,8,10,6,3,7,2 };int w[7] { 0,4,6,2,2,5,1 };int m[100][100];int n 6, c 12;memset(m, 0, sizeof(m));for (int i 1; i n; i){for (int j 1; j c; j){if (j w[i])m[i][j] max(m[i - 1][j], m[i - 1][j - w[i]] v[i]);elsem[i][j] m[i - 1][j];}}for (int i 1; i n; i){for (int j 1; j c; j)cout m[i][j] ;cout endl;}return 0;
}
相关文章：
