动态规划，背包

0-1背包 主要思路

动态规划是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。动态规划则通过类似于填表的方式，把所有子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取出子问题的计数结果，避免了重复计算，从而节约了时间。但是，一般动态规划的问题所用的时间都是以幂次方的形式成倍增加的，很容易超时，这就需要我们将代码做到最优，尽量降低时间复杂度，才能保证题目的完成。

在背包问题中，我们最先接触的是0-1背包问题。它的原理依然是普通的动态规划的原理，这也是最简单的背包形式。

实现过程

w[i]表示物品重量，用v[i]表示物品价值，状态dp[i][j]背包容量d为j时放入前i个物品所能获得的的最大价值。

边界条件：dp[0][j]=dp[i][0]=0;

思路：

对于第i件物品，要装入背包,

(1)当背包的剩余容量小于物品i所需要的容量时，那么物品i不能装入背包，此时，前i件物品装入背包的最大价值就等于前i-1件物品装入背包的最大价值。

(2) 当背包的剩余容量大于物品i所需要的容量时，那么物品i能装入背包，此时有两种情况，物品i可以选择装入或者不装入。如果不装入物品i，那么前i件物品装入背包的最大价值就与前i-1件物品装入背包的最大价值相同,即dp[i][j]=dp[i-1][j]。如果装入物品i，那么此时背包装入物品的最大价值就是 dp[i][j]=dp[i-1][j-w]+v[i]。

此时，比较两个价值选择大的，即：

dp[i][j]=max{ dp[i-1][j] ,dp[i-1][j-w]+v[i]}

if(j >= w[i])
dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);            
else                  
dp[i][j] = dp[i-1][j]; 

完整代码：

共有a件物品，背包的总容量为b，问装入背包总价值是多少。

#include <iostream>
 
using namespace std;
 
int w[105], val[105];
int dp[105][1005];
 
int main()
{
    int a,b;
    cin >> a >> b;
    for(int i=1; i<=a; i++)
        cin >> w[i] >> val[i];
    
    for(int i=1; i<=b; i++) 
        for(int j=b; j>=0; j--)
        {
            if(j >= w[i])
                dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);
            else  
                dp[i][j] = dp[i-1][j];           
        }
    cout << dp[a][b] << endl;
    return 0;
}