关于第三题, 如果仔细观察一下这个图,那么就是每一层的字符都是一样的,这样的话,我们只要实现兜圈子的画法,那么下一层只是一个起点和终点的数据变更. 我们知道了 N*N 的矩形, 那么一共要画几个圈子就知道了, 那就是 (N+1)/2;

listing3.cpp
[CODE]
#include <iostream>
using namespace std;

int main()
{
int N = 15; // to test the situation, you can change the N value;
int x, y;
int i = 0;
char c[N][N];
char b = 'T';

while(i<((N+1)>>1))
{
for(x = i, y = i; x<(N-1-i); x++)
{
if(i == 0)
b = 'T';
else if(i == 1)
b = 'J';
else
{
b = '1' + i - 2;
}
c[x][y] = b;
}
for(x = N - 1 - i, y = i; y<(N-1-i); y++)
{
if(i == 0)
b = 'T';
else if(i == 1)
b = 'J';
else
{
b = '1' + i - 2;
}
c[x][y] = b;
}
for(x = N - 1 - i, y = N - 1 - i; x>=i; x--)
{
if(i == 0)
b = 'T';
else if(i == 1)
b = 'J';
else
{
b = '1' + i - 2;
}
c[x][y] = b;
}
for(x = i, y = N - 1 - i; y>=i; y--)
{
if(i == 0)
b = 'T';
else if(i == 1)
b = 'J';
else
{
b = '1' + i - 2;
}
c[x][y] = b;
}
i++;
}

for(y = 0; y<N; y++)
{
for(x = 0; x<N; x++)
{
cout<<c[x][y];
}
cout<<endl;
}
return 0;
}

[/CODE]

To Kai:

Kai's post for #3

int N = 15;

should be

const int N = 15;

Otherwise, you need to dynmically alloate the 2d array.

/*---------------------------------------------------------------------------
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
http://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);
}

HJin,
你的担心是不必要的.
我给你一段演示代码,你自己一看便明白了:
[CODE]
#include <iostream>
using namespace std;

int main(void)
{
int n;
cin>>n;
char c[n];
for(int i = 0; i<n; i++)
{
c[i] = 'a' + i;
cout<<c[i]<<" ";
}
return 0;
}
[/CODE]

由于考虑到这个N 可以由用户来设定所以我没有将这个N设为常量.
还有想说的是,如果你的程序中可以不用动态开辟空间就不要动态开辟空间, 这是从程序的执行效率考虑.

HJin,
就你的第4题的考虑, 我说一些我的看法:
我对第4题也思考了一下, 方法是用穷举, 但即便是穷举, 书写代码上还是有技巧的, 此外还需要一个自己的计数器, 凭我的直觉, 如果k 很大的话, 那么那个count 将是很大的, 完全有可能超过 2^32 - 1.

还有想说的是,如果你的程序中可以不用动态开辟空间就不要动态开辟空间, 这是从程序的执行效率考虑.

very good idea. Sometimes, I need to work on very large data set, say, an array of size N = 2^21. Then a[N] has to be dynamically allocated.

[CODE]/*---------------------------------------------------------------------------
File name: stack_vs_heap.cpp
Author: HJin
Created on: 6/23/2007 17:47:16
Modification history:
*/
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
const int N = (1<<20);

// does not work since N is too big for a[N] to be on the program stack
// int a[N];
// Okay --- as long as your heap memory is large enough.
int * b = new int [N];
return 0;
}[/CODE]

very good observations. As I mentioned in my original post, enumeration (or brute force) approach is applicable only for n<=6. In fact, n=6 takes too long on my PC to output result.

For n = 7, the number of different Latin squares overflows 32-bit integers.

Yes, there is a lot of places in my code that can be optimized.

HJin,
哈哈, 看来你没有找到合适的方法, 你也没有理解我的关于程序的书写技巧的那句话. 我现在只想告诉你, 不要把没有必要的中间状态带入下一层, 这便是节约内存的根本. 代码我还没有写, 但是凭我的直觉, 这道题如果思考方式不对, 那么是没有可能给出结果的.

我的算法不敢说对任意大的数都有效, 但是k 取个几十, 几百还是可以解的. 由于题目要求输出排列方案, 这自然要影响程序的执行时间, 不过这不会扩展对内存的需要.

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

aipb2007,
你何必问我呢? 你为什么不自己试一下呢? 我既然把代码给出了, 想必不会是假的, 你说是不是?