背包问题

背包问题

当范围很小的背包问题是很容易解决的，而当范围很大\((例如：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;