01背包问题

题目描述

DP41 【模板】01背包

思路

状态表示

第一题：dp[i][j]：前i个物品中选择，总体积不超过j，能挑出来的最大价值
第二题：dp[i][j]：前i个物品中选择，总体积等于j，能挑出来的最大价值（注意：此时要用dp[i][j] == -1来表示选不到总体积等于j的情况）

状态转移

不选i物品的话：dp[i - 1][j]
选i：dp[i - 1][j - v[i]] + w[i] (j - v[i] > 0)
dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])

优化

利用滚动数组进行优化：dp

代码

优化前：

#include<bits/stdc++.h>
using namespace std;
int v[1005], w[1005];
int dp[1005][1005];
int main(){
    int n, V;
    cin>>n>>V;
    for(int i = 1;i <= n; i++)
        cin>>v[i]>>w[i];

    //第一问
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= V; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout<<dp[n][V]<<endl;

    //第二问
    memset(dp, 0, sizeof dp);
    for(int j = 1;j <= V; j++) dp[0][j] = -1;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= V; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i] && dp[i - 1][j - v[i]] != -1) 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    dp[n][V] == -1 ? cout<< 0 : cout<< dp[n][V];
    cout<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

优化后：

#include<bits/stdc++.h>
using namespace std;
int v[1005], w[1005];
int dp[1005];
int main(){
    int n, V;
    cin>>n>>V;
    for(int i = 1;i <= n; i++)
        cin>>v[i]>>w[i];

    //第一问
    for(int i = 1;i <= n; i++)
        for(int j = V;j >= v[i]; j--){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout<<dp[V]<<endl;

    //第二问
    memset(dp, 0, sizeof dp);
    for(int j = 1;j <= V; j++) dp[j] = -1;
    for(int i = 1;i <= n; i++)
        for(int j = V;j >= v[i]; j--){
            if(dp[j - v[i]] != -1) 
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    dp[V] == -1 ? cout<< 0 : cout<< dp[V];
    cout<<endl;
    return 0;
}
~~~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30