动态规划(一）：01背包问题和完全背包问题

动态规划

目录

• 动态规划
• • 1.01背包问题
  • • 1.1题目介绍
    • 1.2思路一介绍(二维数组)
    • 1.3思路二介绍(一维数组) ==空间优化==
    • 1.4思路三介绍(输入数据优化)
    • 2.完全背包问题
    • • 2.1题目描述：
      • 2.2思路一(朴素算法)
      • 2.3思路二(将k优化处理掉)
      • 2.4思路三(优化j的初始条件)
      • 总结

        1.01背包问题

        1.1题目介绍

        

        1.2思路一介绍(二维数组)

        

        代码如下：

        #include
        #include
        using namespace std;
         const int N=1010;
         int v[N],w[N]; //v[N]是物品体积 w[N]是物品的价值
         int f[N][N]; //f[i][j]在体积不超j的前提下，从i个物品中选择最大值
         int main()
         {
             int n,m;
             cin>>n>>m;
             for(int i=1;i
                 cin>v[i]>>w[i];
             }
             for(int i=1;i
                 for(int j=1;j
                     f[i][j]=f[i-1][j];
                     if(j=v[i])//如果我们的背包容量j大于第i个物品的体积，我们在进行决策是否加入第i个物品
                     f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
                 }
             }
             cout
                if(j  v[i] >> w[i];
            for (int i = 1; i = v[i]; j -- )
                    f[j] = max(f[j], f[j - v[i]] + w[i]);
            cout 
            int n, m;   
            cin  n >> m;
            for(int i = 1; i 
                int v, w;
                cin > v >> w;      // 边输入边处理
                for(int j = m; j >= v; j--)
                    f[j] = max(f[j], f[j - v] + w);
            }
            cout 
            cinn>>m;
            for(int i=1;i>v[i]>>w[i];
            for(int i=1;i
                for(int j=0;j
                    for(int k=0;k*v[i]
                        f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
                    }
                }
            }
            cout
            f[i][j] = f[i-1][j];//状态一，即不取第i个物品
            if(j-v[i]=0)//判断是否可以加入第i个物品
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//状态二
        }
        
            cinnm;
            for(int i=1;i
                for(int j=0;j
                    f[i][j]=f[i-1][j];
                    if(j=v[i])
                    {
                        f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
                    }
                }
            }
            cout
        	for(int j=m;j=v[i];j--)
        	{	f[i][j]=f[i-1][j];
        		if(j=v[i])
        		{
        			f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        		}
        	}
        }
        //完全背包问题核心优化后代码
        for(int i = 1 ; i 
            f[i][j] = f[i-1][j];//状态一，即不取第i个物品
            if(j-v[i]=0)//判断是否可以加入第i个物品
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//状态二
        }
        
                    f[j] = max(f[j],f[j-v[i]]+w[i]);
            }
        
            int n,m;
            cinnm;
            for(int i = 1 ; i 
                cinv[i]w[i];
            }
            for(int i = 1 ; i
                    f[j] = max(f[j],f[j-v[i]]+w[i]);
            }
            cout