动态规划算法
原创
动态规划算法将递归算法写成非递归算法，算法把子问题的答案系统的记录在一个表内减少了对子问题的反复求解，提高程序的运行效率。
动态规划算法：需要满足（最优子结构、无后效性、重复子问题）
- 最优子结构：问题的最优解包含子问题的最优解
- 无后效性：某阶段状态一旦确定，不受之后阶段的决策影响
- 重读子问题
零一背包问题
我们有 n 件物品，分别编号为1, 2...n=5。其中编号为i的物品价值为vi={0,6,4,5,3,6}，它的重量为wi={0,4,5,6,2,2}。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是W=10。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？ （每个物品只能使用一次）
解题思路：（好的视频讲解）
- 声明一个dp[n][W]的数组保存动态规划的结果
- 阶段性的工作（一个物品一个物品的循环加入背包，符合判断条件的更新数组内容
- f[i][r] = (f[i-1][r]<f[i-1][r-w[i]]+v[i]) ? f[i-1][r-w[i]]+v[i] : f[i-1][r];（判断条件）
- 找到能够放到某个重量下的物品，得到当前最优解，在前面最优解的基础上得到现阶段整体的最优解。
价值为vi={0,6,4,5,3,6}，重量为wi={0,4,5,6,2,2}
#include <stdio.h>
#define MAXN 20//最多物品数
#define MAXW 100//最大限制重量
//动态规划算法(动态规划数组、质量、价值、W、n)
int knap(int f[MAXN][MAXW],int w[],int v[],int W,int n){
int i,r;
//初始化配置
for(i=1;i<=n;i++){//物品循环
for(r=1;r<=W;r++){//质量递增（）
if(r<w[i])//判断能否放进去。
f[i][r] = f[i-1][r];
else
f[i][r] = (f[i-1][r]<f[i-1][r-w[i]]+v[i])?f[i-1][r-w[i]]+v[i]:f[i-1][r];
printf("%d\t",f[i][r]);
}
printf("\n");
}
return f[n][W];
}
//回推求最优解
int Trackback(int f[MAXN][MAXW],int w[],int x[],int W,int n){
int i,r=W;
int maxw = 0;
for(i=n;i>0;i--)
if(f[i][r]!=f[i-1][r]){
x[i] = 1;
maxw+=w[i];
r = r-w[i];
}else
x[i] = 0;
return maxw;
}
//输出最佳
void display(int x[],int maxw,int maxv,int n){
int i;
printf("最佳背包方案:\n");
for(i=0;i<=n;i++)
if(x[i]==1)
printf("选取%d个物品\n",i);
printf("总重量=%d，总价值=%d\n",maxw,maxv);
}
int main(){
int f[MAXN][MAXW];
int x[MAXN];
int maxv,
maxw;
int n = 5,
W = 10;
int w[MAXN] = {0,4,5,6,2,2};
int v[MAXN] = {0,6,4,5,3,6};
maxv = knap(f,w,v,W,n);
maxw = Trackback(f,w,x,W,n);
display(x,maxw,maxv,n);
return 0;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录