• 长庚123
    了解作者
  • C/C++
    开发工具
  • 3.3MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 1
    下载次数
  • 2020-09-27 08:17
    上传日期
设有n种不同面值的硬币,第i种硬币的币值是vk(其中v1=1),重量是wi,i=1, 2,...,n且现在购买总价值为y的某些商品,需要用这些硬币付款,如果每种钱币使用的个数不限,问如何选择付款的方法使得付出钱币的总重量最轻?设计一个求解该问题的算法,给出算法的伪码描述并分析算法的时间复杂度.假设问题的输入实例是: v1=1,v2=4,v3=6,v4=8 w1=1,w2=2,w3=4,w4=6 y=12 给出算法在该实例上计算的备忘录表和标记函数表,并说明付钱的方法。
FourthExper.zip
  • x64
  • Release
  • FourthExper.pdb
    411KB
  • FourthExper.exe
    15KB
  • FourthExper
  • x64
  • Release
  • link.read.1.tlog
    3.1KB
  • link-cvtres.read.1.tlog
    2B
  • link.command.1.tlog
    1.2KB
  • vc110.pdb
    324KB
  • FourthExper.lastbuildstate
    95B
  • CL.write.1.tlog
    414B
  • cl.command.1.tlog
    558B
  • link-cvtres.write.1.tlog
    2B
  • Դ.obj
    688.9KB
  • link-rc.write.1.tlog
    2B
  • CL.read.1.tlog
    11.9KB
  • FourthExper.log
    1.9KB
  • link.write.1.tlog
    422B
  • link-rc.read.1.tlog
    2B
  • Debug
  • link.read.1.tlog
    2.5KB
  • link-cvtres.read.1.tlog
    2B
  • link.command.1.tlog
    1.1KB
  • vc110.pdb
    332KB
  • FourthExper.lastbuildstate
    95B
  • CL.write.1.tlog
    390B
  • cl.command.1.tlog
    552B
  • vc110.idb
    267KB
  • link-cvtres.write.1.tlog
    2B
  • Դ.obj
    154.7KB
  • link-rc.write.1.tlog
    2B
  • CL.read.1.tlog
    12.1KB
  • FourthExper.log
    1.8KB
  • link.write.1.tlog
    512B
  • link-rc.read.1.tlog
    2B
  • Release
  • link.read.1.tlog
    3KB
  • link-cvtres.read.1.tlog
    2B
  • link.command.1.tlog
    1.2KB
  • vc110.pdb
    308KB
  • FourthExper.lastbuildstate
    97B
  • CL.write.1.tlog
    398B
  • cl.command.1.tlog
    572B
  • link-cvtres.write.1.tlog
    2B
  • Դ.obj
    700KB
  • link-rc.write.1.tlog
    2B
  • CL.read.1.tlog
    12.1KB
  • FourthExper.log
    1.9KB
  • link.write.1.tlog
    398B
  • link-rc.read.1.tlog
    2B
  • FourthExper.vcxproj.filters
    941B
  • FourthExper.vcxproj
    5.6KB
  • Դ.cpp
    1.4KB
  • FourthExper.sdf
    8.3MB
  • FourthExper.v11.suo
    18.5KB
  • FourthExper.sln
    1.2KB
内容介绍
#include<iostream> #include<conio.h> #include <vector> using namespace std; #include <algorithm rel='nofollow' onclick='return false;'> int w[5]; //物品的质量 int v[5]; //物品的价值 int n=4; //物品种类 int y=12; //总价值 int F[5][13]= {0}; //动态规划表 int t[5][13]= {0}; //标记函数 int path[10]= {0}; void findmin() { for (int j = 1; j <= y; j++) { F[1][j]=j*w[1]; t[1][j]=1; } for (int i = 2; i <= n; i++) { for (int j = 1; j <= y; j++) { if(j<0) {F[i][j]=10000;} if(F[i-1][j]>=F[i][j-v[i]]+w[i]) { F[i][j]=F[i][j-v[i]]+w[i]; t[i][j]=i; } else { F[i][j]=F[i-1][j]; t[i][j]=t[i-1][j]; } } } } void traceback() { for (int i = n; i >0 ;) { int temp = t[i][y]; if(temp!=0) path[temp]++; y = y-v[temp]; i = temp; } for (int i = 1; i <=n; i++) { cout<<path[i]<<" "; } } void main() { w[1]=1;w[2]=2;w[3]=4;w[4]=6; v[1]=1;v[2]=4;v[3]=6;v[4]=8; findmin(); cout<<"备忘录表:"<<endl; for (int i = 1; i < 5; i++) { for (int j = 1; j < 13; j++) { cout << F[i][j] << ' '; } cout<<endl; } cout<<endl<<"标记函数表:"<<endl; for (int i = 1; i < 5; i++) { for (int j = 1; j < 13; j++) { cout << t[i][j] << ' '; } cout<<endl; } cout<<endl<<"最小重量为:"; cout<<F[4][12]; cout<<endl<<"付钱的方式为:"; traceback(); getch(); }
评论
    相关推荐