ThirdExper.zip

  • 长庚123
    了解作者
  • C/C++
    开发工具
  • 2.9MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-09-27 08:18
    上传日期
把0-1背包问题加以推广。设有n种物品,第i种物品的价值是vi,重量是wi,体积是ci,且装人背包的重量限制是W,体积是V。问如何选择装人背包的物品使得其总重不超过W,总体积不超过V且价值达到最大?设计一个动态规划算法求解这个问题,说明算法的时间复杂度。
ThirdExper.zip
  • x64
  • Release
  • ThirdExper.exe
    15.5KB
  • ThirdExper.pdb
    411KB
  • ThirdExper
  • x64
  • Release
  • CL.read.1.tlog
    11.7KB
  • link-cvtres.read.1.tlog
    2B
  • ThirdExper.lastbuildstate
    91B
  • vc110.pdb
    324KB
  • cl.command.1.tlog
    554B
  • link-rc.read.1.tlog
    2B
  • Դ.obj
    688.8KB
  • CL.write.1.tlog
    408B
  • ThirdExper.log
    1.9KB
  • link-cvtres.write.1.tlog
    2B
  • link.read.1.tlog
    3.1KB
  • link.command.1.tlog
    1.2KB
  • link.write.1.tlog
    416B
  • link-rc.write.1.tlog
    2B
  • Debug
  • link.10316-cvtres.read.1.tlog
    2B
  • link.6896-rc.read.1.tlog
    2B
  • CL.read.1.tlog
    30.5KB
  • link.11776.read.1.tlog
    2B
  • link.11776.write.1.tlog
    2B
  • link-cvtres.read.1.tlog
    2B
  • ThirdExper.lastbuildstate
    88B
  • vc110.pdb
    348KB
  • link.5348-rc.write.1.tlog
    2B
  • link.10424.read.1.tlog
    2B
  • link.10424.write.1.tlog
    2B
  • link.6896-cvtres.read.1.tlog
    2B
  • link.11776-cvtres.write.1.tlog
    2B
  • cl.command.1.tlog
    536B
  • link-rc.read.1.tlog
    2B
  • link.5348-rc.read.1.tlog
    2B
  • Դ.obj
    155.9KB
  • link.10316-cvtres.write.1.tlog
    2B
  • link.6896-rc.write.1.tlog
    2B
  • link.11776-rc.read.1.tlog
    2B
  • CL.write.1.tlog
    366B
  • link.10316.read.1.tlog
    2B
  • link.5348-cvtres.write.1.tlog
    2B
  • ThirdExper.log
    1.8KB
  • link.10424-cvtres.write.1.tlog
    2B
  • link.5348.write.1.tlog
    2B
  • link.5348.read.1.tlog
    2B
  • link.10316-rc.read.1.tlog
    2B
  • link-cvtres.write.1.tlog
    2B
  • link.10424-rc.write.1.tlog
    2B
  • link.read.1.tlog
    2.4KB
  • link.command.1.tlog
    1.1KB
  • link.write.1.tlog
    480B
  • link.11776-cvtres.read.1.tlog
    2B
  • link.10424-cvtres.read.1.tlog
    2B
  • link.6896.read.1.tlog
    2B
  • link.5348-cvtres.read.1.tlog
    2B
  • link.6896-cvtres.write.1.tlog
    2B
  • link-rc.write.1.tlog
    2B
  • vc110.idb
    475KB
  • link.10316-rc.write.1.tlog
    2B
  • link.10424-rc.read.1.tlog
    2B
  • link.6896.write.1.tlog
    2B
  • link.11776-rc.write.1.tlog
    2B
  • link.10316.write.1.tlog
    2B
  • Դ.cpp
    2KB
  • ThirdExper.vcxproj
    5.6KB
  • ThirdExper.vcxproj.filters
    941B
  • ThirdExper.sln
    1.2KB
  • ThirdExper.sdf
    7.5MB
  • ThirdExper.v11.suo
    21KB
内容介绍
#include<iostream> #include<conio.h> using namespace std; #include <algorithm rel='nofollow' onclick='return false;'> /*int weight[7] = { 0 , 7 , 9 , 11 , 12 , 13 , 14 }; //物品的质量 int volumn[7] = { 0 , 8 , 9 , 10 , 11 , 12, 13 }; //物品的体积 int v[7] = { 0 , 4 , 6 , 8 , 9 , 11 , 12 }; //物品的价值 int n=6; //物品种类 int bagW = 50; //背包重量限制 int bagV = 50; //背包体积限制 int m[7][51][51] = {0}; //动态规划表 int op[7]; //最优解*/ int weight[11] = { 0 , 7 , 9 , 11 , 12 , 13 , 14 , 16 , 17 ,19 , 20}; //物品的质量 int volumn[11] = { 0 , 8 , 9 , 10 , 11 , 12 , 13 , 15 , 16 ,17 , 19}; //物品的体积 int v[11] = { 0 , 4 , 6 , 8 , 9 , 11 , 12 , 14 , 15 , 17, 18}; //物品的价值 int n=10; //物品种类 int bagW = 80; //背包重量限制 int bagV = 80; //背包体积限制 int m[11][81][81] = {0}; //动态规划表 int op[11]; //最优解 void finddp() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= bagW; j++) { for (int k = 1; k <= bagV; k++) { if(k<0 || j<0) m[i][j][k]=-1000; if (j < weight[i] || k < volumn[i]) m[i][j][k] = m[i - 1][j][k]; else m[i][j][k] = max(m[i - 1][j][k], m[i - 1][j - weight[i]][ k - volumn[i]] + v[i]); } } } } void findop(int i, int j, int k) { if (i >= 1) { if (m[i][j][k] == m[i - 1][j][k]) { op[i] = 0; findop(i - 1, j,k); } else if (m[i][j][k] == m[i - 1][j - weight[i]][k - volumn[i]] + v[i]) { op[i] = 1; findop(i - 1, j - weight[i], k - volumn[i]); } } } void print() { int sumV=0,sumW=0; for (int i = 1; i <= n; i++) cout << op[i] << ' '; for (int i = 1; i <= n; i++) { sumW=sumW+op[i]*weight[i]; sumV=sumV+op[i]*volumn[i]; } cout << endl; cout << "总体积为:"<<sumV<<endl; cout << "总质量为:"<<sumW<<endl; } void main() { finddp(); findop(n, bagW, bagV); print(); getch(); }
评论
    相关推荐