0-1背包 每件物品 只能取1件完全背包 每件物品 不限制数量多重背包 每件物品 限制数量混合背包 每件物品 限制数量 或 不限制数量后边的背包问题都在 0-1背包思路上的延伸完全背包问题要会三重循环的写法多重背包 和 混合背包在完全背包问题的三重循环写法上 加个判断条件即可#include bits/stdc.h using namespace std; int w[31],c[31],p[31]; int mx,n; int D01(int m){//01背包问题 int dp[201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int jm;j0;j--){ if(j-w[i]0)dp[j]max(dp[j],dp[j-w[i]]c[i]); } } return dp[m]; } int D1(int m){//完全背包 三层循环 二维数组 int dp[31][201]; memset(dp,0,sizeof(dp)); // for(int i1;in;i){ for(int j0;jm;j){ for(int k0;k*w[i]j;k){ dp[i][j]dp[i-1][j]; if(jk*w[i])dp[i][j]max(dp[i][j],dp[i-1][j-k*w[i]]k*c[i]); } } } return dp[n][m]; } int D2(int m){// 与D1 一样只是代码简化一些 int dp[31][201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int j0;jm;j){ for(int k0;k*w[i]j;k){ dp[i][j]max(dp[i-1][j],dp[i-1][j-k*w[i]]k*c[i]); } } } return dp[n][m]; } int D3(int m){//完全背包 三层循环 滚动数组在D2基础上 优化空间 int dp[201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int jm;j0;j--){ for(int k0;k*w[i]j;k){ dp[j]max(dp[j],dp[j-k*w[i]]k*c[i]); } } } return dp[m]; } int D3A(int m){//多重背包 在D3基础上 K循环里加了一个 (kp[i]) 数量限制 int dp[201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int jm;j0;j--){ //在完全背包的基础上 加了 kp[i] for(int k0;k*w[i]j (kp[i]);k){ dp[j]max(dp[j],dp[j-k*w[i]]k*c[i]); } } } return dp[m]; } int D3B(int m){//混合背包 在D3A基础上 K循环里加了一个 p[i]0 , int dp[201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int jm;j0;j--){ for(int k0;k*w[i]j (kp[i] || p[i]0);k){ dp[j]max(dp[j],dp[j-k*w[i]]k*c[i]); } } } return dp[m]; } int D4(int m){//完全背包 二层循环 滚动数组 int dp[201]; memset(dp,0,sizeof(dp)); for(int i1;in;i){ for(int j0;jm;j){ if(j-w[i]0)dp[j]max(dp[j],dp[j-w[i]]c[i]); } } return dp[m]; } int main(int argc, char** argv) { cinmxn; if(0){//01背包问题 和 全背包 for(int i1;in;i){ cinw[i]c[i]; } } else{//多重背包 for(int i1;in;i){ cinw[i]c[i]p[i]; } } //coutD01(mx);//01背包问题 //完全背包 //coutmaxD1(mx); //coutmaxD2(mx); //coutmaxD3(mx); //coutmaxD4(mx); //混合背包 coutD3B(mx);//混合背包 return 0; }