「动态规划」01背包问题
我是一名初学计算机得菜鸟，这也是我第一次写博客，但这也会让我去查阅更多的资料并且更认真的面对这次。
该问题的基本模板：有n个物品，他们有各自的体积和价值，现有一定容量的背包，如何使该背包装入的物品的价值和最大
| 物品序号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 体积 | 5 | 6 | 7 | 8 |
| 价值 | 5 | 6 | 8 | 10 |
以上我们任意的给了一些数值，为了方便读者的理解。
首先我们先提一下解决动态规划问题的过程
1.定义数组的含义：什么是定义数组的含义呢？我举几个简单的例子：比如你可以用f[2] [2]来储存前三个物品在体积为二的背包中能装的最大价值。
2.找数组之间的关系：这点也是动态规划的最重要一点，也就是所谓的动态转移方程。
3.找方程退出的初始值。
下来我们直接来进入一些题目来进行讲解
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。
接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1
70 3
71 100
69 1
1 2
输出 #1
3
# include <stdio.h>
int main(void){
int m,t;//这里的t就表示的是背包的体积
scanf("%d %d",&t,&m);//对初始两变量的赋值
int a[m];//表示所消耗的时间
int b[m];//所有的价值
int i;
for(i = 0;i < m;++i){
scanf("%d %d",&a[i],&b[i]);
}
int dp[m][t+1];//该数组的含义背包问题上面开始所提到的含义
int j;
for(i = 0;i <= t;++i){
//这里dp的出口
dp[0][i] = 0;
if(i >= a[0])
dp[0][i] = b[0];
}
for(i = 1;i < m;++i){
for(j = 0;j <= t;++j){
dp[i][j] = dp[i - 1][j];//我们总是先定义当前的总是不选第i个的
if(j >= a[i]){
dp[i][j] = dp[i][j] > (dp[i - 1][j - a[i]] + b[i])?dp[i][j] : (dp[i - 1][j - a[i]] + b[i]);//这里就是状态转移方程，从选和不选中找出最大的
}
}
}
printf("%d",dp[m - 1][t]);//这里输出最后一个便是 t体积下的最大价值
return 0;
}
好，这段代码我们就写完了，先来我们在来写一种这段代码的优化
# include <stdio.h>
# define N 1001
int dp[N];
int main(void){
int t,m;//与上面一样
scanf("%d %d",&t,&m);
int w[m],v[m];
int i;
for(i = 0;i < m;++i){
scanf("%d %d",&w[i],&v[i]);
}
int j;
for(i = 0;i < m;++i){
for(j = t;j >= w[i];j--){
//想一想这里为什么反着赋值 tip：该背包的物品都只有一件哦！
dp[j] = dp[j] > dp[j - w[i]] + v[i]?dp[j]:dp[j - w[i]] + v[i];
//遇到问题想一想问什么要定义整体变量而不是局部变量
//想一下这个是如何跳出dp的
}
}
printf("%d",dp[t]);
return 0;
}
这次的分享就此结束
下面我还会写 完全背包问题 和 多重背包问题 感兴趣的可以去我的博客查看哦！
如果有描述不得当的地方希望能够指出。