题意

• n个物品，箱子体积为v，装入物品后，箱子的最小剩余体积是多少

思路

• 动态规划

• 对于每一个物品，考虑放或者不不放，观察体积

• 即维护放入前i个物品能否满足体积为j

• (当前物品已经比需要的体积大了，放不进去)

• (当前物品可以放的进去，考虑放/不放)

• 特别的，本题有三种写法：正常dp，01滚动，就地滚动

• 因为每一行的值之和上一行有关，且我们只在乎最后一行的值，每次更新的时候只用看前一行，所以只用两行来存，一行是当前行，一行是上一行，把原来的行号变成mod2意义下的行号即可（01滚动）

• 由于上一行有的值下一行一定也满足，所以我们可以直接在原有行的基础上改动（就地滚动）

• 注意：如果就地滚动的话要从没维护的开始，到体积无法容纳当前物体为止，避免一个物品被重复维护

  Eg.当前物品体积为三，如果从头开始滚动，到j=3时，dp[3]=dp[0],到j=6时，dp[6]=dp[3]……造成错误

AC代码

#include <bits/stdc++.h>
using namespace std;

int dp[505050];

int main(){
    int v,n;
    cin >> v >> n ;
    int a[50] = {0};
    for(int i=1;i<=n;i++) cin >> a[i]; 
    //v1:正常dp
    // dp[0][0]=1;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<=v;j++){
    //         if(a[i]>j) dp[i][j]=dp[i-1][j];
    //         else dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
    //     }
    // }
    // for(int i=v;i>=0;i--){
    //     if(dp[n][i]){
    //         cout << v-i <<endl;
    //         break;
    //     }
    // }
    //v2:01滚动,压缩到两行内
    // dp[0][0]=1;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j<=v;j++){
    //         if(a[i]>j) dp[i%2][j]=dp[(i-1)%2][j];
    //         else dp[i%2][j] = dp[(i-1)%2][j] || dp[(i-1)%2][j-a[i]];
    //     }
    // }
    // for(int i=v;i>=0;i--){
    //     if(dp[n%2][i]){
    //         cout << v-i <<endl;
    //         break;
    //     }
    // }
    //v3:就地滚动，只占用一行
    dp[0]=1;
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){
            if(dp[j-a[i]]) dp[j] = dp[j-a[i]];
        }
    }
    for(int i=v;i>=0;i--){
        if(dp[i]){
            cout << v-i <<endl;
            break;
        }
    }
    return 0;
}