当前位置：首页 > news >正文

动态规划-背包问题——[模版]01背包(背包母题)

news 2024/11/15 6:08:49

1.题目解析

题目来源

[模版]01背包_牛客题霸_牛客网

测试用例

2.算法原理

1.状态表示

第一小问：求最大价值

第二小问：求充满时的价值

2.状态转移方程

第一小问：求最大价值

第二小问：求充满时的价值

3.初始化

第一小问：求最大价值

第二小问：求充满时的价值

4.填表顺序

从上到下，每一行从左到右

5.返回值

返回dp[n][V]，第一小问代表在[1,n]个物品取出总体积不大于V的物品的最大总价值

第二小问代表在[1,n]个物品中取出物品体积恰好为V的总价值

3.实战代码

#include <iostream>
#include <string.h>
using namespace std;const int N = 1010;
int dp[N][N];
int w[N];
int v[N];
int n,V;int main()
{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]);}}}cout<<(dp[n][V] == -1 ? 0 : dp[n][V])<<endl;return 0;
}

代码解析

4.优化代码(主要针对空间的优化)

#include <iostream>
#include <string.h>
using namespace std;const int N = 1010;
int dp[N];
int w[N];
int v[N];
int n,V;int main()
{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]);}}}cout<<(dp[V] == -1 ? 0 : dp[V])<<endl;return 0;
}