动态规划之 0-1背包 完全背包 多重背包 混合背包
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 i=1;i<=n;i++){ for(int j=m;j>=0;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 i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k*w[i]<=j;k++){ dp[i][j]=dp[i-1][j]; if(j>=k*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 i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;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 i=1;i<=n;i++){ for(int j=m;j>=0;j--){ for(int k=0;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循环里加了一个 (k<=p[i]) 数量限制 int dp[201]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ for(int j=m;j>=0;j--){ //在完全背包的基础上 加了 k<=p[i] for(int k=0;k*w[i]<=j && (k<=p[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 i=1;i<=n;i++){ for(int j=m;j>=0;j--){ for(int k=0;k*w[i]<=j && (k<=p[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 i=1;i<=n;i++){ for(int j=0;j<=m;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) { cin>>mx>>n; if(0){//01背包问题 和 全背包 for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } } else{//多重背包 for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]>>p[i]; } } //cout<<D01(mx);//01背包问题 //完全背包 //cout<<"max="<<D1(mx); //cout<<"max="<<D2(mx); //cout<<"max="<<D3(mx); //cout<<"max="<<D4(mx); //混合背包 cout<<D3B(mx);//混合背包 return 0; }