题解 | #[NOIP2001]装箱问题#

很奇怪的一道题，这样做居然要过不去 居然不压成一维就对了，其他情况就错了

#include<bits/stdc++.h>
using  namespace  std;
const  int  N=20000;
int  a[N];
int  dp[N];
int  main()
{
    int  v,n;
    cin>>v>>n;
    for(int  i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int  i=1;i<=n;i++)
    {
        for(int j=v;j>=a[i];j--)
        {
           dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
        cout<<v-dp[v];
}

这里要写第二道题

#include<bits/stdc++.h>   
using namespace std; 
  
const int N = 20010; 
int a[N]; // 存储物品体积的数组  
int dp[N][N]; // 动态规划数组，dp[i][j]表示前i个物品放入容量为j的箱子时的最大体积  
  
int main()  
{  
    int n, v; // n表示物品数量，v表示箱子容量  
    cin >> v >> n; // 输入箱子容量和物品数量  
  
    for(int i = 0; i < n; i++) // 遍历所有物品  
    {  
        cin >> a[i]; // 输入第i个物品的体积  
    }  
  
    // 初始化dp数组，所有dp[0][j]都为0，表示没有物品时箱子内的体积为0  
//     for(int j = 0; j <= v; j++)  
//     {  
//         dp[0][j] = 0;  
//     }  
  
    // 动态规划填充dp数组  
    for(int i = 1; i <= n; i++) // 遍历所有物品  
    {  
        for(int j = 0; j <= v; j++) // 遍历所有可能的箱子容量  
        {  
            // 如果当前箱子容量j小于第i个物品的体积a[i-1]，则不能放入该物品，直接继承前一个物品时的最大体积  
            if(j < a[i-1])  
            {  
                dp[i][j] = dp[i-1][j];  
            }  
            // 否则，可以选择放入或不放入第i个物品，取两种情况中的较大值  
            else  
            {  
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1]] + a[i-1]);  
            }  
        }  
    }  
    cout << v - dp[n][v] << endl;  
    return 0; 
}这里值得注意的就是下标问题，下标问题必须要仔细思考