FourthExper.zip

#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(); }