题目描述
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;
}
优化后：
#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;
}
~~~