动态规划求解找零问题和背包问题 C++代码

//动态规划求解硬币找零问题

#include

#include

using namespace std;

//int values[] 保存不同种类硬币的面值

//int valueKinds 硬币的种类

//int money 所需找零的面值

//int coinsUsed[i] 所需找零面值的最少硬币数

void makeChange(int values[], int valueKinds, int money, int coinsUsed[])

{

coinsUsed[0] = 0;

for (int cents = 1; cents <= money; cents++)

{

int minCoins = cents; //给所需最少硬币数赋初始值

for (int kind = 0; kind < valueKinds; kind++)

{

if (values[kind] <= cents) //如果当前面值小于找零面值

{

int temp = coinsUsed[cents - values[kind]] + 1; //将找零面值cents分解为cents和values[kind]两种面值

if (temp < minCoins)

minCoins = temp;

}

}

coinsUsed[cents] = minCoins; //保存cents面值所需最少找零硬币数量

cout<<\"the value:\"<}

}

int main()

{

int coins[] = {100,25,10,5,1}; //硬币按照降序排列，可以使用排序算法

int money, coinsUsed[1000]; //所需找零面值,保存所需最小硬币数

cin>>money;

assert(money>=100);

makeChange(coins,5 , money, coinsUsed);

system(\"PAUSE\");

}

//动态规划求解背包问题

#include

int V[200][200];//前i个物品装入容量为j的背包中获得的最大价值

int max(int a,int b)

{

if(a>=b)

return a;

else return b;

}

int KnapSack(int n,int w[],int v[],int x[],int C)

{

int i,j;

for(i=0;i<=n;i++)

V[i][0]=0;

for(j=0;j<=C;j++)

V[0][j]=0;

for(i=0;i<=n-1;i++)

for(j=0;j<=C;j++)

if(jV[i][j]=V[i-1][j];

else

V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);

j=C;

for(i=n-1;i>=0;i--)

{

if(V[i][j]>V[i-1][j])

{

x[i]=1;

j=j-w[i];

}

else

x[i]=0;

}

printf(\"选中的物品是:\\n\");

for(i=0;iprintf(\"%d \

printf(\"\\n\");

return V[n-1][C];

}

void main()

{

int s;//获得的最大价值

int w[15];//物品的重量

int v[15];//物品的价值

int x[15];//物品的选取状态

int n,i;

int C;//背包最大容量

n=5;

printf(\"请输入背包的最大容量:\\n\");

scanf(\"%d\

printf(\"输入物品数:\\n\");

scanf(\"%d\

printf(\"请分别输入物品的重量:\\n\");

for(i=0;iscanf(\"%d\

printf(\"请分别输入物品的价值:\\n\");

for(i=0;iscanf(\"%d\

s=KnapSack(n,w,v,x,C);

printf(\"最大物品价值为:\\n\");

printf(\"%d\\n\

while(1);

}