c++01背包完全背包多重背包问题(动态规划求解)

之前在屈老的课上用的是动态规划解，现在有机会看到b站某视频的动态规划求解的具体写法，故在此更新博文，今天虽然大年初一，但不减学习热情。

0-1背包二维数组1版本只需要从前往后遍历就行了。

10 4
2 1
3 3
4 5
7 9

输出

12

#include
using namespace std;
int dp[35][205];
int w[35],c[35];
int main(){
    int m,n;
    cin >> m >> n;
    for(int i =1;i<=n;i++){
        cin >> w[i] >> c[i];
    }
    for(int i =1;i<=n;i++){
        for(int j =1;j<=m;j++){
            if(j 
0-1背包(一维数组版本) 
这里要逆着写遍历。具体如下
 
10 4
2 1
3 3
4 5
7 9
 
输出
 
12
 
#include
using namespace std;

int w[35],c[35],dp[205];
int main()
{
    int n,m;
    cin >> m >> n;
    for(int i =1;i<=n;i++){
        cin >> w[i] >> c[i];
    }
    for(int i =1;i<=n;i++){
        for(int j = m;j>=1;j--){
            if(j>=w[i])
                dp[j] = max(dp[j],dp[j-w[i]]+ c[i]);
        }
//        for(int k=0;k<=m;k++){
//            cout << dp[k] << " ";
//        }
        cout << endl;
    }
    cout << dp[m];
    return 0;
}
 
完全背包 
完全背包与0-1背包代码类似，但是它是顺着遍历
 测试样例
 
10 4
2 1
3 3
4 5
7 9
 
输出
 
12
 
#include
using namespace std;

int w[50],c[50],dp[210];
int main(){
    int m,n;
    cin >> m >> n;
    for(int i= 1;i<=n;i++)
        cin >> w[i] >> c[i];
    for(int i = 1;i<=n;i++)
        for(int j =w[i];j<=m;j++)
            dp[j] = max(dp[j],dp[j-w[i]]+c[i]);
    cout << "max = "  << dp[m];
    return 0;

}
 
多重背包 
相当于对0-1背包进行限制
 测试样例
 
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
 
输出:1040
 
#include
using namespace std;

int v[510],w[510],s[510],dp[6100];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];
    for(int i =1;i<=n;i++){
        for(int j =m;j>=1;j--){
            for(int k =0;k<=s[i]&& j>=k*v[i];k++){
                dp[j] = max(dp[j],dp[j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout << dp[m];
}
 
二维背包 
测试数据
 
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
 
输出结果
 
129
 
模仿0-1背包，修改一下
 
#include
using namespace std;

int n,m,k,a[1010],b[1010],c[1010],dp[30][100];

int main(){
    cin >> m >> n >> k;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;
    for(int i =1;i<=k;i++) cin >> a[i] >> b[i] >> c[i];

    for(int i =1;i<=k;i++){
        for(int j =m;j>=0;j--){
            for(int l = n;l>=0;l--){
                if(j<=a[i] && l<=b[i]) dp[j][l] = min(dp[j][l],c[i]);
                else{
                    int x,y;
                    if(j-a[j]<0) x=0;else x=j-a[i];
                    if(l-b[i]<0) y=0;else y=l-b[i];
                    dp[j][l] = min(dp[j][l],dp[x][y]+c[i]);
                }
            }
        }
    }
    cout << dp[m][n];

}