当范围很小的背包问题是很容易解决的，而当范围很大\((例如：1\le n\le 100,1\le w_i\le10^7,1\le v_i\le 100,1\le W\le 10^9)\)时，就应该换一种 dp 的表示方式，这样才能够降低其复杂度。
\(dp[i+1][j]\)表示前 i 个物品中挑选出价值总和为 j 时总重量的最小值
\(\begin{cases}dp[0][0]=0\\dp[0][j]=INF\\dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]) \end{cases}\)
代码：
fill(dp[0],dp[0]+maxn*maxv+1,inf);
dp[0][0]=0;
for(int i=0;i<n;++i)
for(int j=0;j<=maxn*maxv;++j)
if(j<v[i]) dp[i+1][j]=dp[i][j];
else dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);
int ans=0;
for(int i=0;i<=maxn*maxv;++i)
if(dp[n][i]<=W) ans=i;原文：https://www.cnblogs.com/CADCADCAD/p/12193738.html