f******5
发帖数: 11 | 1 //Algorithm DPKnapsack(w[1..n], v[1..n], W)
// var V[0..n,0..W], P[1..n,1..W]: int
// for j := 0 to W do
// V[0,j] := 0
// for i := 0 to n do
// V[i,0] := 0
// for i := 1 to n do
// for j := 1 to W do
// if w[i] j and v[i] + V[i-1,j-w[i]] > V[i-1,j] then
// V[i,j] := v[i] + V[i-1,j-w[i]]; P[i,j] := j-w[i]
// else
// V[i,j] := V[i-1,j]; P[i,j] := j
// return V[n,W] and the optimal subset by backtracing
//choose three items that will fit into a knapsack of capacity 5
#include
using namespace std;
void knapsack(int *weight, int *value, int num, int capacity);
void knapsack(int *weight, int *value, int num, int capacity){
int V[num+1][capacity+1];
int K[num+1][capacity+1];
for (int j=0; j
V[0][j]=0;
} //initialize the value matrix first row
for (int i=0; i
V[i][0]=0;
}//initialize the value matrix[][] first column
for(int i=0; i
for(int j=0; j
K[i][j]=0;
V[i][j]=0;
}
for (int i=1; i
for (int w=1; w
if(w>=weight[i]&&value[i]+V[i-1][w-weight[i] ]> V[i-1][w])
{
K[i][w]=1;//K is the keep matrix determing whether to keep
item i
V[i][w]= value[i]+V[i-1][(w-weight[i])];//V is the value
matrix indicating the current value in the sack
} //value[i] is the value of worth in item i branch put
item i into the sack and leave availabe w-weight[i] for i-1 th item
else
{
K[i][w]=0;//not the keep item i in the sack so 0
V[i][w]=V[i-1][w]; //value of present comprenesive item
number updated by 1 lesss than total item
}
}//end of inner for loop inside double for loop reassign the value
matrix and keep matrix
}//end of outer for loop i represents the item 1, 2,3
for (int i=num, j=capacity; i>0;i--) {
if (K[i][j]==1)//start from the bottom right corner of Keep matrix
of capacity weight and total item
{
cout<<"put into the backsack item number#: "<
j=j-weight[i];
}
}
for (int i=1;i
for (int j=1; j
{
cout<
}
cout<
}
for (int i=1;i
for (int j=1; j
{
cout<
}
cout<
}
}
int main(void)
{
int weight[]={0,3,2,1};
int value[]={0,5,3,4};
int capacity=5;
int num=3;
knapsack(weight, value, num, capacity);
system("pause");
return 0;
} |
|
