#include?“knapsack.h“

#include?
#include?
#include?
#include?


void?knapsack（int?v[]int?w[]?int?cint?n?int**m）?
{?
	int?jmax?=?std::min（w[n]-1c）;?

	for（int?j=0;j<=jmax;j++）?
		m[n][j]=0;?
	for（int?jj=w[n];jj<=c;jj++）?
		m[n][jj]=v[n];?
	for（int?i=n-1;i>1;i--）	//?recursive?O（nc）
	{?
		jmax?=?std::min（w[i]-1?c）;?
		for（int?j?=?0;j?<=?jmax;j++）?
			m[i][j]?=?m[i+1][j];?
		for（int?jj?=?w[i];jj?<=?c;?jj++）?
			m[i][jj]?=?std::max（m[i+1][jj]?m[i+1][jj-w[i]]+v[i]）;?
	}?
	m[1][c]?=?m[2][c];?

	if（c>=w[1]）?
		m[1][c]?=?std::max（m[1][c]?m[2][c-w[1]]+v[1]）;			//?m[1][c]?maximum?value

}?

void?traceback（int?**mint?w[]int?cint?nint?x[]）?
{?
	for（int?i=1;i		if（m[i][c]==m[i+1][c]）?x[i]=0;?
		else?{x[i]=1;?	c-=w[i];}?

	x[n]=（m[n][c]）?1:0;?
}?

void?printx（?const?int?n?const?int?c?int*?x?int**?m?）
{
	std::cout<<“最優(yōu)解：“<	for?（int?j?=?1;?j?	{
		std::

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????655??2011-08-27?09:13??knapsack.h

?????文件???????1927??2011-10-31?21:18??knapsack.cpp

-----------?---------??----------?-----??----

?????????????????2582????????????????????2