[算法总结] 动态规划 -- 背包背包！

1. 01背包题目介绍

有 N 件物品和一个容量为 V 的背包，每件物品有各自的价值且只能被选择一次，

要求在有限的背包容量下，装入的物品总价值最大。

思路:

• 迭代n次 枚举每次物品在每个体积的拿法
• 迭代m次 枚举能拿的体积
• 条件判断 如果枚举的体积小于本身的体积那么拿不起 所以我们只能 = f[i-1][j]
• 如果我们能拿的起,那么我们需要和f[i-1][j-v[i]]+w[i]来比较

代码实现(二维背包):

int n, m;   
cin >> n >> m;
for(int i = 1; i > v[i] >> w[i]; 

for(int i = 1; i  w[i];
    for(int i = 1; i = v[i]; j--) 
            f[j] = max(f[j], f[j-v[i]]+w[i]);
    cout  m;
    for(int i = 1; i > v[i] >> w[i];
    for(int i = 1; i >w[i]>>s[i];

for(int i=1;i=0;j--)
    {
        for(int k=1;km;
    for(int i=1;i>s[i];
        for(int j=0;j>v[i][j]>>w[i][j];
    }
    for(int i=1;i=0;j--)
        {
            for(int k=0;k