虽然大佬已经为我们罗列了背包九讲：https://blog.csdn.net/m0_37809890/article/details/83153974
但是我觉得自己还是要再罗列
01背包
有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。
其中每种物品都只有一件。
令dp[i][j]来表示前i件物品装入容量为j的背包所能得到的最大总价值。
对于dp[i][j]来说，i指的是前i件物品，j指的是还剩下多少背包空间
memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&value[i]);//输入价值 for(int i=1;i<=n;i++) scanf("%d",&volume[i]);//输入体积 for(int i=1;i<=n;i++) for(int j=0;j<=v;j++) if(j<volume[i])//如果背包体积小于物品体积，就看放前一个物品后的体积 dp[i][j]=dp[i-1][j];//j存放的是放进去的体积 else dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);//与前一个进行比较，看看前一个的价值与这当下价值哪个更大进行保存 printf("%d\n",dp[n][v] );
优化之后
int n=read(),v=read(); for(int i=1;i<=n;i++)value[i]=read(); for(int i=1;i<=n;i++)volume[i]=read(); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=v;j>=volume[i];j--) dp[j]=max(dp[j],dp[j-volume[i]]+value[i]); printf("%d\n",dp[v] );
原文：https://www.cnblogs.com/-113/p/12319149.html