之前在屈老的课上用的是动态规划解，现在有机会看到b站某视频的动态规划求解的具体写法，故在此更新博文，今天虽然大年初一，但不减学习热情。
0-1背包(二维数组版本)
0-1背包二维数组1版本只需要从前往后遍历就行了。
10 42 13 34 57 9
输出
12
#includeusing 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 42 13 34 57 9
输出
12
#includeusing 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 42 13 34 57 9
输出
12
#includeusing 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 100080 20 440 50 930 50 740 30 620 20 1
输出:1040
#includeusing 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 6053 36 12010 25 1295 50 2501 45 1304 20 119
输出结果
129
模仿0-1背包，修改一下
#includeusing 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];}