首先上一个神级的教程，背包九讲 这个教程讲解详细，读懂了大有裨益。 还有一篇比较有帮助：https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html 首先是一个完全背包问题(恰好装满）：https://vjudge.net/contest/263202#problem/A
AC code: #include<bits/stdc++.h> using namespace std; const int maxn = 125; int dp[maxn+5][maxn + 5]; int n = 0; void solve(){ fill(dp[0],dp[0]+(maxn+5)*(maxn+5),0);//详情见背包九讲的初始化问题 for(int i = 0;i <= maxn;++i){//初始化，这是合法状态 dp[1][i] = 1; } for(int i = 1;i <= maxn;++i){//恰好装满 dp[i][0] = 1; } for(int i = 2;i <= maxn;++i){ for(int j = 1;j <= maxn;++j){ dp[i][j] = dp[i-1][j] + (j >= i ? dp[i][j-i]:0); } } } int main(){ solve(); while(~scanf("%d",&n)){ printf("%d\n",dp[n][n]); } return 0; }接下来是一个多重背包问题：https://vjudge.net/contest/263202#problem/B
AC code: #include<bits/stdc++.h> using namespace std; const int maxn = 300; int dp[18][maxn + 5];//dp[i][j]表示使用前i种货币，凑出j元的方法数 int n = 0; void solve(){ fill(dp[0],dp[0]+18*(maxn+5),0); for(int i = 0;i <= maxn;++i){ dp[1][i] = 1; } for(int i = 1;i <= 17;++i){//要初始化为1 dp[i][0] = 1; } for(int i = 2;i <= 17;++i){ for(int j = 1;j <= maxn;++j){ dp[i][j] = dp[i-1][j] + (j >= i*i? dp[i][j-i*i]:0);//i,j状态由只是用前i-1种货币 //凑成j元的方法数+使用前i种货币j-i元（在加上i元货币）的方法数 } } /* for(int i = 1;i <= 4;++i){ for(int j = 0;j <= 4;++j){ printf("%d%c",dp[i][j],(j == 10)?'\n':' '); } } */ } int main(){ solve(); while(~scanf("%d",&n) && n != 0){ printf("%d\n",dp[17][n]); } return 0; }上面两个问题的初始化是一样的。背包九讲有段话话很重要 初始化的细节问题： 我们看到的求解最优解的背包问题中，事实和桑有两种不太相同的问法。
要求”背包恰好装满“ 时的最优解不要求背包一定要被装满时的最优解我们上面所讨论的就是第2种， 不要求背包一定要被装满时的最优解。 一种区别这两种问法的实现方法是在初始化的时候有所不不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 dp[0]dp[0] 为0, 其他dp[1…W]均设为−∞dp[1…W]均设为−∞ ，这样就可以保证最终得到 dp[W]dp[W] 是一种恰好装满背包的最优解 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将dp[0…W]dp[0…W] 全部设为0。
这是为什么呢？可以这样理解：初始化的dpdp 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装的状态下被 “恰好装满” ，此时背包价值为0。其他容量的背包均没有合法的解，属于未定义的状态，所以都应该被赋值为 −∞−∞ 。当前的合法解，一定是从之前的合法状态推得的
如果背包并非必须被装满，那么任何容量的背包都有一个合法解 “什么也不装”，这个解的价值为0,所以初始化时状态的值也就全部为0了。 接下来还是一个多重背包的问题：https://vjudge.net/contest/263202#problem/C
AC code: #include<bits/stdc++.h> using namespace std; const int maxn = 8e3 ; int num[4]; int val[4] = {0,1,2,5}; bool dp[maxn+10]; void solve(){ int ma = num[1] + 2*num[2] + 5*num[3]; fill(dp,dp+maxn+10,false); dp[0] = true; for(int i = 1;i <= 3;++i){ for(int k = 1;k <= num[i];++k){ for(int j = ma;j >= 1;--j){ dp[j] = (dp[j] || dp[j-val[i]]); //cout << i << " " << j << " " << dp[j] << endl; } } } for(int i = 1;i <= ma+1;++i){ if(dp[i] == false){ printf("%d\n",i); return ; } } } int main(){ while(~scanf("%d %d %d",&num[1],&num[2],&num[3])){ if(num[1] == 0 && num[2] == 0 && num[3] == 0){ break; } solve(); } return 0; }加了最大值最小值限制的多重背包：https://vjudge.net/contest/263202#problem/R
AC code: #include<bits/stdc++.h> using namespace std; const int maxn = 100 + 10; int dp[maxn][maxn][maxn];//dp[i][j][k]表示使用了i种水果，有了j个盘，在第i种水果使用了k个 struct node{ int mi,ma; }; node num[maxn]; #define INF 1e6 int n = 0,m = 0; void solve(){ fill(dp[0][0],dp[0][0]+maxn*maxn*maxn,0); for(int i = 1;i <= m;++i){//非法状态初始化为-1 dp[0][i][0] = -INF; } for(int i = num[1].mi;i <= num[1].ma;++i){//第一个盘子的初始化 dp[1][i][i] = 1; } for(int i = 2;i<= n;++i){ for(int j = 0;j <= m;++j){ for(int k = num[i].mi;j +k <= m && k <= num[i].ma;++k){ for(int l = num[i-1].mi;l <= num[i-1].ma;++l){ if(dp[i-1][j][l] == -INF){ continue; } dp[i][j+k][k] += dp[i-1][j][l];//由第i-1种转移而来，所以要遍历i-1种的情况 } } } } int ans = 0; for(int i = num[n].mi;i <= num[n].ma;++i){//第n种水果使用了i个的种数 ans += dp[n][m][i];//答案要把他们加起来 } printf("%d\n",ans); } int main(){ while(~scanf("%d %d",&n,&m)){ for(int i = 1;i <= n;++i){ scanf("%d %d",&num[i].mi,&num[i].ma); } solve(); } return 0; }