[全民编程]76道高难度C++练习题.含NOI竞赛题.欢迎挑战

/*---------------------------------------------------------------------------
File name: C76-48.cpp
Author: HJin
Created on: 6/18/2007 15:15:52

C76-48.cpp --- the cpp source file for solving the 48th of the 76
classical C/C++ problems.

经典 76 道编程题 之 48:

48. 将４个红球，３个白球与３个黄球排成一排，共有多少种排法？

Answer: binomial(10, 4) * binomial(6, 3) * binomial(3, 3) = 4200.

Analysis:

Allocate r+w+y (=10) slots. The job can be done in three steps:
(1) we put all r red balls into the r+w+y slots --- total is binomial(r+w+y, r)
(2) we put all w white balls into the remaining w+y slots --- total is binomial(w+y, y)
(3) we put all y yellow balls into the remaining y slots --- total is binomial(y, y) = 1

All in all, total is binomial(r+w+y, r) * binomial(w+y, y) * 1.

Programming thoughts:

Generate all 3^(r+w+y) possible choices (since each slot can have one of the
three colors ) and check if a choice is valid. A choice is valid if and only
if there are r red balls, w white balls, and y yellow balls.

We used a set in the implementation, since set does not store duplicates.

Sample output:

1 rrwy
2 rryw
3 rwry
4 rwyr
5 ryrw
6 rywr
7 wrry
8 wryr
9 wyrr
10 yrrw
11 yrwr
12 ywrr
total number of different combinations are 12
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#include <set>
#include <string>
using namespace std;

string buffer;

/**
Time complexity is O(3^(r+w+y)) --- very inefficient.

build the set of all combinations.
*/
void buildSet(int r, int w, int y, int n, set<string>& s);

/**
wrap the function buildSet() and outputs results.
*/
int combination(int r, int w, int y, bool print = true);
/**
check if the string is valid.

A choice is valid if and only if there are r red balls, w white balls, and
y yellow balls.
*/
bool isValid(int r, int w, int y, string& str);

int main(int argc, char** argv)
{
// test #3
//int r=4;
//int w=3;
//int y=3;

// test #2
//int r=3;
//int w=2;
//int y=2;

// test #1
int r=2;
int w=1;
int y=1;

cout<<"total number of different combinations are "<<combination(r, w, y, true)<<endl;

return 0;
}

void buildSet(int r, int w, int y, int n, set<string>& s)
{
if(n==0)
{
if(isValid(r, w, y, buffer))
{
s.insert(buffer);
}

return;
}

string temp = buffer; // keep previous state

buffer+="r";
buildSet(r, w, y, n-1, s);

buffer = temp; // recall previous state
buffer+="w";
buildSet(r, w, y, n-1, s);

buffer = temp; // recall previous state
buffer+="y";
buildSet(r, w, y, n-1, s);
}

int combination(int r, int w, int y, bool print)
{
set<string> s;
int n = r+w+y;
int counter = 0;

buildSet(r, w, y, n, s);

if(print) // print combinations
{
for(set<string>::const_iterator iter = s.begin(); iter!=s.end(); ++iter)
{
++counter;
cout<<counter<<"\t"<<*iter<<endl;
}
}

return s.size();
}

bool isValid(int r, int w, int y, string& str)
{
int r_=0; // store # of red balls
int w_=0;
int y_=0;
bool res = false;

for(size_t i =0; i<str.size(); ++i)
{
switch(str[i])
{
case 'r':
++r_;
break;
case 'w':
++w_;
break;
case 'y':
++y_;
break;
}
}

res = (r_==r) && (w_==w) && (y_==y);

return res;
}

[此贴子已经被作者于2007-6-19 6:17:01编辑过]

/*---------------------------------------------------------------------------
File name: C76-13.cpp
Author: HJin
Created on: 6/18/2007 15:15:52

C76-13.cpp --- the cpp source file for solving the 13th of the 76
classical C/C++ problems.

经典 76 道编程题 之 13:

13. 有N个硬币（N为偶数）正面朝上排成一排，每次将 N-1 个硬币翻过来放在原位
置， 不断地重复上述过程，直到最后全部硬币翻成反面朝上为止。编程让计算机把
翻币的最简过程及翻币次数打印出来（用＊代表正面，O 代表反面）。

Analysis:

Since we are changing the states of N-1 items each time, there is one coin which
keeps its previous state.

1 --- 正面 (or ＊)
0 --- 反面

1 1 1 1 (original state: #0)
0 0 0 1 (#1 --- keeps N = 4)
1 1 0 0 (#2 --- keeps N-1 = 3)
0 1 1 1 (#3 --- keeps N-2 = 2)
0 0 0 0 (#4 --- keeps N-3 = 1)

This is true for the general case N.

Sample output:

＊ ＊ ＊ ＊
0 0 0 ＊
＊ ＊ 0 0
0 ＊ ＊ ＊
0 0 0 0
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

void print(const vector<bool>& v);
int tossCoins(int n);

int main(int argc, char** argv)
{
tossCoins(4);

return 0;
}

int tossCoins(int n)
{
vector<bool> v;
int i;
int j;

// orginal state
v.resize(n);
for(i=0; i<n; ++i)
v[i] = true;
print(v);

for(i=n-1; i>=0; --i)
{
for(j=0; j<n; ++j)
v[j] = !v[j];
v[i] = !v[i]; // keeps v[i]

print(v);
}

return n;
}

void print(const vector<bool>& v)
{
for(vector<bool>::const_iterator iter = v.begin(); iter != v.end(); ++iter)
{
if(*iter)
cout<<setw(4)<<"＊";
else
cout<<setw(4)<<"0";
cout<<" ";
}
cout<<endl;
}

/*---------------------------------------------------------------------------
File name: C76-17.cpp
Author: HJin
Created on: 6/18/2007 18:21:10

C76-17.cpp --- the cpp source file for solving the 17th of the 76
classical C/C++ problems.

经典 76 道编程题 之 17:

17. 编写一个程序，当输入不超过６０个字符组成的英文文字时，计算机将这个句子
中的字母按英文字典字母顺序重新排列，排列后的单词的长度要与原始句子中的长度
相同。例如：

输入：

ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ

输出：

ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ

并且要求只对Ａ到Ｚ的字母重新排列，其它字符保持原来的状态。

Analysis:

This is really a counting sort problem --- count how many letters A to Z.

Sample output:

THE PRICe OFBREAD IS $1.25 PER POUND
ABC DDEEE EFHIINO OP $1.25 PPR RRSTU
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#include <iomanip>
using namespace std;

/**
counting sort to sort the letters 经典 76 道编程题 之 17.

Space complexity: O(1).
Time complexity: O(strlen(s)).
*/
void counting_sort(char* s);

int main(int argc, char** argv)
{
char s[] = "THE PRICe OFBREAD IS $1.25 PER POUND";

cout<<s<<endl;

counting_sort(s);
cout<<s<<endl;

return 0;
}

void counting_sort(char* s)
{
/**
c[0] --- stores how many letter A in s
c[1] --- stores how many letter B in s
...
c[25] --- stores how many letter Z in s
*/
int c[26];
int n =strlen(s);
int i;
int j;

// initiate counters to 0
for(j=0; j<26; ++j)
{
c[j] = 0;
}

for(i=0; i<n; ++i)
{
// toupper() does not affect non-alpha letters.
s[i] = toupper(s[i]);
}

// count number of different capital letters
for(i=0; i<n; ++i)
{
if(s[i] >='A' && s[i] <='Z')
{
j = 0+ (s[i] - 'A') ;
++c[ j ];
}
}

i=0;

/**
Although there are two loops here, it is NOT O(25* n).
It is O(n), since i is incremented c[j] times for each j,
and c[0] + c[1] + ... +c[25] <= n.
*/
for(j=0; j<25; ++j)
{
while (c[j] > 0)
{
if(s[i]>='A' && s[i]<='Z')
{
s[i] = 'A'+j;
--c[j]; // used 1 letter, so counter goes down by 1
}
++i;
}
}
}

/*---------------------------------------------------------------------------
File name: C76-1.cpp
Author: HJin
Created on: 6/18/2007 22:53:55

C76-1.cpp --- the cpp source file for solving the 1st of the 76
classical C/C++ problems.

经典 76 道编程题 之 1:

1. 给定等式 A B C D E 其中每个字母代表一个数字，且不同数字对应不
D F G 同字母。编程求出这些数字并且打出这个数字的
+ D F G 算术计算竖式。

───────

X Y Z D E

Analysis:

Let A = a[0], B = a[1], ..., Z = a[9], where the array a
is a permutation of the ten digits. The easist way is to
loop over all 10! = 3,628,800 possible permutations for the array a,
and check if the result holds.

C++ has a next_permutation (or prev_permutation) function template
for permutations.

A B C D E F G X Y Z
==============================
a[ 0 1 2 3 4 5 6 7 8 9 ]

Sample output:

A = 2, B = 9, C = 7, D = 8, E = 6,
F = 5, G = 0, X = 3, Y = 1, Z = 4.

2 9 7 8 6
8 5 0
+ 8 5 0
--------------------------------------
= 3 1 4 8 6
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#define DIM(x) sizeof((x)) / sizeof ( (x)[0] )
#include <algorithm>

using namespace std;

/**
check the result for a permutation.
*/
bool check(int *a);

/**
print result.
*/
void print(int *a);

int main(int argc, char** argv)
{
int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
bool res = check(a);
if(res)
print(a);

// when next_permutation returns false, we permute
// all 10! choices. Time complexity is O(10!)
while( std::next_permutation(a, a+DIM(a)) )
{
res = check(a);
if(res)
print(a);
}

return 0;
}

bool check(int *a)
{
int carry; // carry
bool res;
int temp;

// 1st vertical equation
temp = a[4] + 2*a[6];
res = ( ( temp % 10) == a[4] );
if(!res)
return false;
carry = temp / 10;

// 2nd vertical equation
temp = a[3] + 2*a[5] + carry;
res = res && ( (temp % 10) == a[3] );
if(!res)
return false;
carry = temp / 10;

// 3rd vertical equation
temp = a[2] + 2*a[3] + carry;
res = res && ( ( temp % 10) == a[9] );
if(!res)
return false;
carry = temp / 10;

// 4th vertical equation
temp = a[1] + carry;
res = res && ( ( temp % 10) == a[8] );
if(!res)
return false;
carry = temp / 10;

// 5th vertical equation
temp = a[0] + carry;
res = res && ( ( temp % 10) == a[7] );
if(!res)
return false;

return true;
}

void print(int *a)
{
cout<<"A = "<<a[0]<<", ";
cout<<"B = "<<a[1]<<", ";
cout<<"C = "<<a[2]<<", ";
cout<<"D = "<<a[3]<<", ";
cout<<"E = "<<a[4]<<",\n";
cout<<"F = "<<a[5]<<", ";
cout<<"G = "<<a[6]<<", ";
cout<<"X = "<<a[7]<<", ";
cout<<"Y = "<<a[8]<<", ";
cout<<"Z = "<<a[9]<<".\n\n";

cout<<" "<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<"\n";
cout<<" "<<a[3]<<" "<<a[5]<<" "<<a[6]<<"\n";
cout<<"+ "<<a[3]<<" "<<a[5]<<" "<<a[6]<<"\n";
cout<<"--------------------------------------\n";
cout<<"= "<<a[7]<<" "<<a[8]<<" "<<a[9]<<" "<<a[3]<<" "<<a[4]<<"\n";
}

第三题挑个简单的

#include "stdio.h"

main()
{
char s[21][21];
char c[]={'T','J','1','2','3','4','5','6','7','8','9'};
int input,i,j;
printf("enter the number betweent 3 to 20");
scanf("%d",&input);
if(input<3||input>20)
{
printf("what you want ");
getch();
return;
}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
s[i][j]='0';

}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
printf("%c",s[i][j]);
printf("\n");
}

for(i=input;i>=0;i--)
{
for(j=i;j<=input-i;j++)
{
s[j][i]=c[i];
s[i][j]=c[i];
s[input-i][input-j]=c[i];
s[input-j][input-i]=c[i];
}

}
for(i=0;i<=input;i++)
{
for(j=0;j<=input;j++)
printf("%c",s[i][j]);
printf("\n");
}
getch();
}

/*---------------------------------------------------------------------------
File name: C76-24.cpp
Author: HJin
Created on: 6/18/2007 22:53:55

C76-24.cpp --- the cpp source file for solving the 24th of the 76
classical C/C++ problems.

经典 76 道编程题 之 24:

24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班，
向东要走Ｍ块，向北要走Ｎ块，（见图）。请设计一个程序，由计算机寻找并
打印出所有的上班的路径。

单位

┬ ┌─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │ │
│ ├─┼─┼─┼─┼─┼─┼─┤
↓ │ │ │ │ │ │ │ │
Ｎ ├─┼─┼─┼─┼─┼─┼─┤
↑ │ │ │ │ │ │ │ │
│ ├─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │
┴ └─┴─┴─┴─┴─┴─┴─┘
家 ├─────→Ｍ←─────┤

Analysis:

Let us

E --- the person move 1km to the east;
N --- to stand for the person move 1km to the east;

If M= 7, N =4 (as in the figure), then

E E E E E E E N N N N

means that the person travels east 7km first, then he/she travels
north 4km.

A little bit math shows that we have

binomial(M+N, M)

different ways to travel from home to work, since we have to travel
M kms to the east. A way is a choice that how we put the M E's into
M+N slots.

Sample output (for M=5, N=2):

1 EEEEENN
2 EEEENEN
3 EEEENNE
4 EEENEEN
5 EEENENE
6 EEENNEE
7 EENEEEN
8 EENEENE
9 EENENEE
10 EENNEEE
11 ENEEEEN
12 ENEEENE
13 ENEENEE
14 ENENEEE
15 ENNEEEE
16 NEEEEEN
17 NEEEENE
18 NEEENEE
19 NEENEEE
20 NENEEEE
21 NNEEEEE
correct.
Press any key to continue . . .

Reference:

1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>
#include <string>
#include <set>
using namespace std;

/**
serious improvment needed: this recursive version is very inefficient.
For M=7, N=4, it takes 3 mintues to compute.

The classical algorithm to permute a string. We use a set to keep
different strings --- some permutations may repeat.

*/
void way_recursive(string& in, string& out, set<string>& ss);

/**
a wrapper of way_recursive.
*/
int way(int M, int N, bool print=true);

/** compute binomial(n, k).
* n >=k
*
*
*/
int binomial(int n, int k); // n choose k

int main(int argc, char** argv)
{
// test #1: --- the recursive way takes long time (3 mintues)
//int M=7;
//int N=4;

// test #2:
int M=5;
int N=2;

int num;

num = way(M, N);

/**
A little bit math shows that the number is binomial(M+N, M).
This is just a check to give you more confidence.
*/
if(num != binomial(M+N, M))
cout<<"wrong number.\n";
else
cout<<"correct.\n";

return 0;
}

void way_recursive(string& in, string& out, set<string>& ss)
{
// in is empty so that all chars are transferred to out buffer
// and out is a permutation of in
if( in.empty() )
{
ss.insert(out); // insert only one copy --- no duplicates
return;
}

// the way to permute a string in one statement
for(size_t i=0; i<in.size(); ++i)
way_recursive(in.substr(0, i) + in.substr(i+1), out+in[i], ss);
}

int way(int M, int N, bool print)
{
set<string> ss;
string in;
string out;
int i;
int counter = 0;

in.resize(M+N);

// the very first way
for(i=0; i<M; ++i)
in[i] = 'E';
for(i=M; i<M+N; ++i)
in[i] = 'N';

// build the set
way_recursive(in, out, ss);

if(print)
{
for(set<string>::const_iterator iter = ss.begin(); iter != ss.end(); ++iter)
{
++counter;
cout<<counter<<"\t"<<*iter<<endl;
}
}

return counter;
}

int binomial(int n, int k)
{
int res = 1;
int i;

if(k>n/2)
k = n-k;

++n;
for(i=1; i<=k; ++i)
{
res *= (n-i);
res /= i;
}

return res;
}

Happy holiday to you! Admire you have "zhongzi"..... no Chinese food in this small town for me.

/*---------------------------------------------------------------------------
File name: C76-19.cpp
Author: HJin
Created on: 6/19/2007 22:53:55

6/20/2007 11:43:57
-----------------------------------------------------------
Add the soln for fractional Knapsack problem and some comments
about the algorithms.

6/19/2007 23:49:34
-----------------------------------------------------------
Add the soln for 0-1 Knapsack problem and move the 2d memory
functions from my namespace directly into this file.

C76-19.cpp --- the cpp source file for solving the 19th of the 76
classical C/C++ problems.

经典 76 道编程题 之 19:

19. (背包问题) 有 N 件物品 d1，......dN，每件物品重量为 W1，..., WN
(Wi > 0)， 每件物品价值为 V1，......VN (Vi>0)。用这N件物品的某个子集
填空背包，使得所取物品的总重量<=TOTAL，并设法使得背包中物品的价值尽可
能高。

Analysis:

In English, this is called the Knapsack problem, in which you are helping
a thief to maximize his loot from a store.

There are two versions of this problem: the 0-1 Knapsack problem and the
fractional Knapsack problem. In the 0-1 Knapsack problem, an item is either
taken or discarded --- you cannot take 0.1 part of an item. In the fractional
Knapsack problem, items can be divided into fractions, say, 0.5.

In general, the the 0-1 Knapsack problem can be solved by a dynamic programming
algorithm, whereas the fractional Knapsack problem can be solved by a greedy
algorithm.

The dynamic programming algorithm needs to first establish a table c[0..n, 0..W],
where n is the number of items, W is the max weight the knapscak can hold.
c[i, w] stands for the max-value for i items and w pounds --- we need to find
c[n, W]. By a math analysis:

c[i, w] = 0, if i=0 or w=0
= c[i-1, w], if i>0 and w_i < w
= max(v_i + c[i-1, w-w_i], c[i-1, w]), if i>0 and w_i < w

The greedy algorithm need to first choose the most valuable item ---
the one with highest value per pound, and then the second most valuable,
and so on.

Sample output

~~~~~ Knapsack problem (0-1) ~~~~~
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 6 6 6 6 6 6 6 6 6 6 6 6 6
0 0 7 7 7 7 13 13 13 13 13 13 13 13 13 13 13
0 0 7 8 8 15 15 15 15 21 21 21 21 21 21 21 21
0 0 7 8 8 15 15 16 17 21 24 24 24 24 30 30 30
0 0 7 8 11 15 18 19 19 26 26 27 28 32 35 35 35
0 0 7 8 11 15 20 20 27 28 31 35 38 39 39 46 46

The thief's max-profit loot choices are:
(20, 6) (11, 4) (8, 3) (7, 2)
( loot weight / max weight = 15 / 16 )
loot value is 46
loot weight is 15

~~~~~ Knapsack problem (fractional) ~~~~~
1
1
1
1
0.2
0
1 * 7 + 1 * 20 + 1 * 11 + 1 * 8 + 0.2 * 9 = 47.8
Press any key to continue . . .

Note that I used an array of 2 columns to store v_i and w_i's.
The first column is for the values;
The second column is for the weights.
The reason is that I need to sort the items by decreasing values per pound
for a greedy algorithm.

Reference:
0. Cormen, Introduction to algorithms, 2nd ed, MIT press.
1. 野比, 相当经典的76道编程自虐题分享.无答案 at
https://bbs.bc-cn.net/viewthread.php?tid=147853
*/

#include <iostream>

#include <string>
#include <sstream>
#include <iomanip>
#define DIM(x) sizeof( (x) ) / sizeof( (x)[0] )

#define hj_debug

using namespace std;

/**
Dynamic programming algorithm for solving the 0-1 knapsack problem.

Space complexity is Theta( n W).
Time complexity is Theta( n W).
*/
int Knapsack01(int (*a)[2], int n, int W);

/**
trackback the optimal soln --- recursive version.
*/
void TrackBack01_recursive(int (*a)[2], int** c, int i, int w);

/**
trackback the optimal soln --- loop version.
*/
void TrackBack01_loop(int (*a)[2], int** c, int i, int w);

/**
Greedy algorithm for solving the fractional Knapsack problem.
*/
double KnapsackFractional(int (*a)[2], int n, int W, double* x);

/**
Track back the optimal soln.
*/
void TrackBackFractional(int (*a)[2], double* x, int n, double maxValue);

/**
Insertion sort to sort the array by decreasing value. The most value item
is the one which has the largest value per pound.
*/
void sortDecreasing(int (*a)[2], int n);

/**
auxilliary functions for 2d array dynamic allocation and deallocation.
*/
template <typename T>
inline T** new2d(int row, int col);

template <typename T>
inline T** new2dInit(int row, int col);

template <typename T>
inline T** new2dInit2(int row, int col);

template <typename T>
inline void delete2d(T** arr2d, int row);

template <typename T>
inline T max2(const T&a, const T& b);

int main(int argc, char** argv)
{
// test #1
//int a[][2] = {
// {60, 10},
// {100, 20},
// {120, 30},
//};

int a[][2] = {
{6, 4},
{7, 2},
{8, 3},
{9, 5},
{11, 4},
{20, 6},
};
int W = 16;
double x[DIM(a)];

cout<<"\n~~~~~ Knapsack problem (0-1) ~~~~~\n";
Knapsack01(a, DIM(a), W);

cout<<"\n~~~~~ Knapsack problem (fractional) ~~~~~\n";
KnapsackFractional(a, DIM(a), W, x);

return 0;
}

int Knapsack01(int (*a)[2], int n, int W)
{
int** c = new2dInit2<int>(n+1, W+1);
int w;
int i;
int lootValue;

for(i=1; i<=n; ++i)
{
for(w=1; w<=W; ++w)
{
c[i][w] = (a[i-1][1] <= w ?
max2(a[i-1][0] + c[i-1][ w-a[i-1][1] ],
c[i-1][w]) : c[i-1][w]);
}
}
lootValue = c[n][W];

#ifdef hj_debug
for(i=0; i<=n; ++i)
{
for(w=0; w<=W; ++w)
cout<<setw(4)<<c[i][w];
cout<<endl;
}
cout<<endl;
#endif

TrackBack01_loop(a, c, n, W);
//TrackBack01_recursive(a, c, n, W);

delete2d(c, n+1);
return lootValue;
}

void TrackBack01_recursive(int (*a)[2], int** c, int i, int w)
{
if(i==0)
{
cout<<endl;
}
else
{
if(c[i][w] == c[i-1][w] )
{
TrackBack01_recursive(a, c, i-1, w);
}
else
{
cout<<"("<<a[i-1][0]<<", "<<a[i-1][1]<<") ";
TrackBack01_recursive(a, c, i-1, w-a[i-1][1]);
}
}
}

void TrackBack01_loop(int (*a)[2], int** c, int i, int w)
{
ostringstream oss;
int val=0;
int weight = 0;
int maxWeight = w;

while(i>0 && w>0)
{
--i;
if( c[i+1][w] != c[i][w] )
{
val += a[i][0];
weight += a[i][1];

oss<<"("<<a[i][0]<<", "<<a[i][1]<<") ";
w-=a[i][1];
}
}

cout<<"The thief's max-profit loot choices are:\n";
cout<<oss.str()<<endl;
cout<<"( loot weight / max weight = "<<weight<<" / "<<maxWeight<<" )"<<endl;
cout<<"loot value is "<<val<<endl;
cout<<"loot weight is "<<weight<<endl;
}

double KnapsackFractional(int (*a)[2], int n, int W, double* x)
{
double lootValue=0;
int i;

for (i=0; i<n; ++i)
x[i] = 0;
int w = 0;

sortDecreasing(a, n);

i=0;
while (w < W)
{
if ( w + a[i][1] <= W )
{
x[i] = 1; // take whole item i
w += a[i][1];
lootValue += a[i][0];
}
else
{
// take fractional parts of item i
// this is the last time that we can
// add an item to the knapsack.
x[i] = double(W - w) / a[i][1];
w = W;
lootValue += x[i] *a[i][0];
}
++i;
}

for(i=0; i<n; ++i)
cout<<x[i]<<endl;

TrackBackFractional(a, x, n, lootValue);

return lootValue;
}

void TrackBackFractional(int (*a)[2], double* x, int n, double maxValue)
{
int i=0;

for(i=0; i<n-1; ++i)
{
if(x[i] > 0)
{
cout<< x[i] <<" * " << a[i][0];
}
else
break;

if(x[i+1] == 0)
cout<< " = "<<maxValue;
else
cout<<" + ";
}

if(x[n-1] >0)
cout<<x[n-1] << " * "<< a[n-1][0] << " = " << maxValue;

cout<<endl;
}

void sortDecreasing(int (*a)[2], int n)
{
for(int out = 1; out<n; ++out)
{
int in = out;
int v = a[out][0];
int w = a[out][1];

while( in >0 && double(a[in-1][0]) / a[in-1][1] < double(v)/w )
{
a[in][0] = a[in-1][0];
a[in][1] = a[in-1][1];
--in;
}

a[in][0] = v;
a[in][1] = w;
}
}

template <typename T>
T** new2d(int row, int col)
{
T** arr2d = new T*[row];
for(int i=0; i<row; ++i)
arr2d[i] = new T[col];

return arr2d;
}

template <typename T>
T** new2dInit(int row, int col)
{
T** arr2d = new T*[row];
int i;
int j;

for(i=0; i<row; ++i)
arr2d[i] = new T[col];

for(i=0; i<row; ++i)
for(j=0; j<col; ++j)
arr2d[i][j] = T();

return arr2d;
}

template <typename T>
T** new2dInit2(int row, int col)
{
T** arr2d = new T*[row];
int i;
int j;

for(i=0; i<row; ++i)
arr2d[i] = new T[col];

for(i=0; i<row; ++i)
arr2d[i][0] = T();

for(j=0; j<col; ++j)
arr2d[0][j] = T();

return arr2d;
}

template <typename T>
void delete2d(T** arr2d, int row)
{
for(int i=0; i<row; ++i)
delete [] arr2d[i];

delete [] arr2d;
}

template <typename T>
T max2(const T&a, const T& b)
{
return (a>b ? a: b);
}

这里数组的大小不是必须要在编译时为常量吗？kai，你这样可以吗？

我大致看了下HJin对这个问题的解法，我如果写，我也会有个同样的问题，不仅这个问题，一切有关类似这样的递归回溯的问题都存在，比如皇后，比如我在46楼写那个题。

我很想看看kai你是怎么处理当n很大时的情况。当然，不要让程序一直运行个几天才算出来，呵呵~（我想的话）。

说的很有道理，但是递归对内存的开销并不都是不必要啊。难道所有的递归算法都可以被迭代取代而不用到栈？
期待你的solution，这样说不好懂。

呵呵