[数据结构与算法]bp问题，萌新记录生活用的大佬勿喷

最近打算开始努力去搞一搞动态规划，所以本篇博客持续更新

1.背包问题

c代表价格，d代表价值；

（1）01背包

有n件商品他们都有各自的价格和价值，问我总共有w得钱可以买到的最大价值的是多少 每件商品只可以买一次

朴素转移方程

for(int i=1;i<=n;i++){
 ? ?for(int j=1;j<=w;j++){
 ? ? ? ?if(c[i]<=j){
 ? ? ? ? ? ?dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+d[i]);
 ? ? ?  }else
 ? ? ? ? ? ?dp[i][j]=dp[i-1][j];
 ?  }
}//dp[i][j]意义是用j元钱，可以在前i件物品中买的最大价值

01背包优化

for(int i=1;i<=n;i++){
    for(int j=w;j>=c[i];j--){
        dp[j]=max(dp[j],dp[j-c[i]]+d[i]);
    }
}//dp[i]代表用i的容量可以得到的最大价值

（2）多重背包

每件商品都有一个数量k限制，最多可以买k个

for(int i=1;i<=n;i++){
    for(int j=1;j<=w;j++){
        if(c[i]<=j){
            int count = min(n[i], j/c[i]);//判断我第i件商品可以买多少次
            for(int k=0;k<=count;k++){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*c[i]]+k*d[i]);
            }
        }
    }
} 
?

（3)完全背包

每件物品可以买无限多次

for(int i=1;i<=N;i++){
            for(int j=v[i];j<=V;j++){
             ? ?dp[j]=max(dp[j],dp[j-v[i]]+w[i]);   
            } 
        }