动态规划经典例题,C++解决01背包,车间资源分配,硬币兑换问题

网站建设800 更新时间：2025-06-08 13:08:50

2023年8月1日发(作者：)

动态规划经典例题，C++解决01背包，车间资源分配，硬币兑换问题在M件物品取出若⼲件放在空间为W的背包⾥，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最⼤价值的⽅案。注意：在本题中，所有的体积值均为整数。//01背包#includeusing namespace std;int main(){ int c,n; //容量，物品个数 int i,j; cin>>c>>n; int *w=new int[n+1]; int *v=new int[n+1];

for(i=0;i>w[i]>>v[i];

int **dp=new int*[n+1]; for( i=0;i<=n;i++) dp[i]=new int[n+1];

for(i=0;i<=n;i++) { dp[0][i]=0; dp[i][0]=0; }

for(i=1;i<=n; i++) { for(j=0;j<=c;j++) { if(j < w[i])

dp[i][j]= dp[i-1][j]; else

dp[i][j]= max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } cout<

delete[] dp; return 0; }

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、⽅程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故⼀定要仔细体会上⾯基本思路的得出⽅法，状态转移⽅程的意义，以及最后怎样优化的空间复杂度。再看⼀个例⼦：资源分配问题//资源分配问题/*某⼚根据计划安排，拟将n台相同的设备分配给m个车间，各车间获得这种设备后，可以为国家提供盈利Ci j(i台设备提供给j号车间将得到的利润，1≤i≤n，1≤j≤m)

。问如何分配，才使国家得到最⼤的盈利？*/

#include#include#includeusing namespace std;const int n=30; //测试⽤例：30台设备const int m=10; //10个车间int max(int a,int b){ return a>b?a:b; }

int main(){ int p[n+1][m+1]={0}; //p[i][j]表⽰i台设备分配给前j号车间最⼤利润 int c[n+1][m+1]={0}; //c[i][j]表⽰i台给第j号车间所得利润。 int i=0,j=0; clock_t starttime,endtime; srand((unsigned)time(NULL)); //随机数种⼦初始化

starttime=clock(); //开始时间

for(i=1;i<=n;++i) for(j=1;j<=m;++j) c[i][j]=(rand()%9)+1; //范围：(0,1000)

for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { p[i][j]=p[i][j-1]; for(int k=0;k<=i;++k) p[i][j]=max(p[i][j],(p[i-k][j-1]+c[k][j]));

} }

endtime=clock();

cout<<"利润表(第i⾏j列表⽰i台给设备第j号车间所得利润)："<

for(j=1;j<=m;++j) cout<

cout<

for(i=0;i<=n;++i) { for(j=0;j<=m;++j) { cout<

} cout<

return 0;

}这⾥取n=4,m=2的运⾏结果：看另⼀个动态规划例⼦：硬币兑换怎么样才能⽤最少的硬币凑出给出的⾦额？//动态规划的零钱兑换，不是贪⼼//求零钱的最少数量组合，每种硬币不限个数

#include#includeusing namespace std;int coinchange(vector coins,int num){ int result[num+1]={0}; //num[i]表⽰i块钱需要的最少零钱数

for(int i=1;i<=num;++i) { int min=INT_MAX;

for(int j=0;j<();++j) { int left=i-coins[j]; //假设coins[j]可以花掉 if(left>=0 && result[left]!=-1) //-1代表不能凑出这个⾦额 { min=(result[left]

result[i]=(min==INT_MAX)?-1:min+1; //这个组合可以，数⽬+1

} } return result[num];}int main(){ vector test; _back(1); _back(3); _back(5); //可以⽤的硬币种类

cout<

2023年8月1日发(作者：)

动态规划经典例题，C++解决01背包，车间资源分配，硬币兑换问题在M件物品取出若⼲件放在空间为W的背包⾥，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最⼤价值的⽅案。注意：在本题中，所有的体积值均为整数。//01背包#includeusing namespace std;int main(){ int c,n; //容量，物品个数 int i,j; cin>>c>>n; int *w=new int[n+1]; int *v=new int[n+1];

for(i=0;i>w[i]>>v[i];

int **dp=new int*[n+1]; for( i=0;i<=n;i++) dp[i]=new int[n+1];

for(i=0;i<=n;i++) { dp[0][i]=0; dp[i][0]=0; }

for(i=1;i<=n; i++) { for(j=0;j<=c;j++) { if(j < w[i])

dp[i][j]= dp[i-1][j]; else

dp[i][j]= max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } cout<

delete[] dp; return 0; }

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、⽅程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故⼀定要仔细体会上⾯基本思路的得出⽅法，状态转移⽅程的意义，以及最后怎样优化的空间复杂度。再看⼀个例⼦：资源分配问题//资源分配问题/*某⼚根据计划安排，拟将n台相同的设备分配给m个车间，各车间获得这种设备后，可以为国家提供盈利Ci j(i台设备提供给j号车间将得到的利润，1≤i≤n，1≤j≤m)

。问如何分配，才使国家得到最⼤的盈利？*/

#include#include#includeusing namespace std;const int n=30; //测试⽤例：30台设备const int m=10; //10个车间int max(int a,int b){ return a>b?a:b; }

int main(){ int p[n+1][m+1]={0}; //p[i][j]表⽰i台设备分配给前j号车间最⼤利润 int c[n+1][m+1]={0}; //c[i][j]表⽰i台给第j号车间所得利润。 int i=0,j=0; clock_t starttime,endtime; srand((unsigned)time(NULL)); //随机数种⼦初始化

starttime=clock(); //开始时间

for(i=1;i<=n;++i) for(j=1;j<=m;++j) c[i][j]=(rand()%9)+1; //范围：(0,1000)

for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { p[i][j]=p[i][j-1]; for(int k=0;k<=i;++k) p[i][j]=max(p[i][j],(p[i-k][j-1]+c[k][j]));

} }

endtime=clock();

cout<<"利润表(第i⾏j列表⽰i台给设备第j号车间所得利润)："<

for(j=1;j<=m;++j) cout<

cout<

for(i=0;i<=n;++i) { for(j=0;j<=m;++j) { cout<

} cout<

return 0;

}这⾥取n=4,m=2的运⾏结果：看另⼀个动态规划例⼦：硬币兑换怎么样才能⽤最少的硬币凑出给出的⾦额？//动态规划的零钱兑换，不是贪⼼//求零钱的最少数量组合，每种硬币不限个数