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

文档介绍：〃动态规划求解硬币找零问题
#include <iostream>
#include <>
using namespace std;
//int values[]
//int valueKinds
//int m〃动态规划求解硬币找零问题
#include <iostream>
#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:"<<cents<<"needs minimum coins is:"<<minCoins<<endl;
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