01背包问题
第一次深入接触动态规划背包问题，看了好多博主的文章，写一点关于自己的理解~~~
背包问题的关键在于对表达式f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}的理解。
引用一个最普通的例子：a,b,c,d,e5件商品，重量分别为2,2,6,5,4质量分别为6,3,5,4,6
一个承重为10的背包，如何让背包里装的物品拥有最大的价值？？
f[i][j]表示最大价值（i个物品放入承重为j的背包里）
w[i]表示第i件物品的重量。
p[i]表示第i件物品的价值。
就某件商品来说，可带可不带
（1）如果不带的话价值不会发生改变，依然是上一件物品的情况，价值为f[i-1][j]。
（2）如果要带的话，那需要背包空出这件物品所需要的空间，也就是j-w[i],同时再加上这件物品的价值为w[i]。即f[i-1][j-w[i]]+p[i];
最大价值就是f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+p[i])
- for(i=1;i<=n;++i)
- {
- for(j=0;j<=w;++j)
- {
- if(j<w[i])
- f[i][j]=f[i-1][j];
- else
- f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+p[i]);
- }
- }
从前者的基础上得到后者，将一个问题分解成子问题。
Input输入的第一行有两个整数T（1 <= T<= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
Output输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
Sample Input
70 3
71 100
69 1
1 2
Sample Output
3
#include<iostream>
using namespace std;
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int T;int m;
cin>>T>>m;
int dp[100][100];
int t[100],v[100];
for (int i =0; i<=m; i++)
dp[i][0] = 0; // 第一行和第一列都赋值为0
for (int j = 0; j<=T;j ++)
dp[0][j] = 0;
for(int i=1;i<=m;i++)
{
cin>>t[i]>>v[i];
}
for(int i=1;i<=m;i++)//参考上图表格 可知从1~m赋值
{
for(int j=1;j<=T;j++)
{
if(j>=t[i])//j<t[i]时根本不能采药
dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
cout<<dp[m][T]<<endl;
return 0;
}