Description

有n種基礎的投資項目，每一種的單位收益率為profitn，存在m種投資組合，限制每一種的投資總額不能超過invest_summ
每種投資組合中項目所需的單位投入是不同的，為costmn

求：使得收益率之和最高的每種項目投資的單位數

Input

• 兩個整數：n(項目種類數，范圍：1≤n<20)，m(投資組合數，1≤m<20)
• 一行長度為n的2位小數：profitn(單位收益率，0<profitn<1)
• 一行長度為m的整數：invest_summ(某組合的限制投資總額，invest_summ>0)
• m行長度為n的整數：costmn(某組合中某項目的單位投入，costmn>0)

Output

• 輸出n個以空格間隔的8位小數，表示每一個項目投資的單位量。
• 如果有多個最優解，輸出任意一個。

Sample

#0

Input

Copy

4 3  
0.13 0.75 0.25 0.44  
20 7 50  
5 3 2 1  
2 1 1 1  
7 12 9 2  

Output

Copy

0.00000000 3.60000000 0.00000000 3.40000000

Hint

max Σprofit x
s.t. cost x<= invest_sum, x>=0

線性規劃公式秒了

#include<iostream>
#include<cmath>
#include"stdio.h"
using namespace std;
#define M 10000
double kernel[110][310];
int m = 0, n = 0, t = 0;
void input()
{cin>>n;cin>>m;// m = 3;int i, j;//初始化核心向量for (i = 0; i <= m + 1; i++)for (j = 0; j <= n + m + m; j++)kernel[i][j] = 0;for (i=1;i<=n;i++)cin>>kernel [0][i];for(i=1;i<=m;i++){cin>>kernel[i][n+2];}for (i=1;i<=m;i++){// cout<<"    不等式"<<i<<"  ";for (j=1;j<=n+2;j++){if(j==n+1){kernel[i][j]=1;}else if(j==n+2){}else{cin>>kernel [i][j];}}}for (i = 1; i <= m; i++){kernel[i][0] = kernel[i][n + 2];kernel[i][n + 2] = 0;}
//-1最大值
//1最小值t = -1;if (t == -1)for (i = 1; i <= n; i++)kernel[0][i] = (-1)*kernel[0][i];for (i = 1; i <= m; i++){kernel[i][n + i] = kernel[i][n + 1];if (i != 1)kernel[i][n + 1] = 0;}
}//算法函數
void comput()
{int i, j, flag, temp1, temp2, h, k = 0, temp3[100];double a, b[110], temp, temp4[110], temp5[110], f = 0, aa, d, c;for (i = 1; i <= m; i++)temp3[i] = 0.0000;for (i = 0; i < 11; i++){temp4[i] = 0.000;temp5[i] = 0.0000;}for (i = 1; i <= m; i++){if (kernel[i][n + i] == -1){kernel[i][n + m + i] = 1;kernel[0][n + m + i] = M;temp3[i] = n + m + i;}elsetemp3[i] = n + i;}for (i = 1; i <= m; i++)temp4[i] = kernel[0][temp3[i]];do {for (i = 1; i <= n + m + m; i++){a = 0;for (j = 1; j <= m; j++)a += kernel[j][i] * temp4[j];kernel[m + 1][i] = kernel[0][i] - a;}for (i = 1; i <= n + m + m; i++){if (kernel[m + 1][i] >= 0) flag = 1;else{flag = -1;break;}}if (flag == 1){for (i = 1; i <= m; i++){if (temp3[i] <= n + m) temp1 = 1;else{temp1 = -1;break;}}if (temp1 == 1){// cout << " 此線性規劃的最優解存在!" << endl << endl << "  最優解為：" << endl << endl << "     ";for (i = 1; i <= m; i++)temp5[temp3[i]] = kernel[i][0];for (i = 1; i <= n; i++)f += t * kernel[0][i] * temp5[i];for (i = 1; i <= n; i++){if(i==1){printf("%.8f",temp5[i]);}else{printf(" %.8f",temp5[i]);}//                     cout << "x" << i << " = " << temp5[i];
//                    printf("")
//                     if (i != n)
//                     cout << "， ";}cout<<endl;// cout << " ;" << endl << endl << "     最優目標函數值f= " << f << endl << endl;
//                printf("%.6f\n",f);return;}else{// cout << " 此線性規劃無解" << endl << endl;return;}}if (flag == -1){temp = 100000;for (i = 1; i <= n + m + m; i++)if (kernel[m + 1][i] < temp){temp = kernel[m + 1][i];h = i;}for (i = 1; i <= m; i++){if (kernel[i][h] <= 0) temp2 = 1;else {temp2 = -1;break;}}}if (temp2 == 1){// cout << "此線性規劃無約束";return;}if (temp2 == -1){c = 100000;for (i = 1; i <= m; i++){if (kernel[i][h] != 0)  b[i] = kernel[i][0] / kernel[i][h];if (kernel[i][h] == 0)  b[i] = 100000;if (b[i] < 0)     b[i] = 100000;if (b[i] < c){c = b[i];k = i;}}temp3[k] = h;temp4[k] = kernel[0][h];d = kernel[k][h];for (i = 0; i <= n + m + m; i++)kernel[k][i] = kernel[k][i] / d;for (i = 1; i <= m; i++){if (i == k)continue;aa = kernel[i][h];for (j = 0; j <= n + m + m; j++)kernel[i][j] = kernel[i][j] - aa * kernel[k][j];}}} while (1);return;
}int main()
{input();for(int i=1;i<n;i++){for(int j=1;j<m+2;j++){// cout<<kernel[i][j]<<" ";}// cout<<endl;}comput();// int a = 0;// scanf("%d", &a);// cout<<f<<endl;return 0;
}