ALGO-21 算法训练装箱问题(c++)

墨蓝 2022-12-11 12:18 143阅读 0赞

dp思路：  
dp\[i\]\[j\]表示前i个物品，放入容量为j的背包能占用的最大体积  
对过程中的任意状态：  
若 temp > j 则无法将第i个物品放入，所以dp\[i\]\[j\] = dp\[i-1\]\[j\];  
若 temp <= j 那么  
（1）若将第i个物品放入背包，那么dp\[i\]\[j\] = dp\[i-1\]\[j-temp\] + temp;  
这句话的意思是，前i个物品，放入容量为j的背包能占用的最大体积等于  
前i-1个物品放入j-temp的背包占的最大体积 再加上 temp。  
然后比较两个数的大小，取最大值。

所以dp\[n\]\[k\] = max(dp\[n-1\]\[k\], dp\[n-1\]\[k-temp\[n\]\] + temp\[n\]);  
我再理解理解

再理解：  
这应该是01背包问题，  
对于一个物品之放和不放两种状态  
每次输入一个物品的体积  
就假设背包的体积 从 1 - V开始遍历，  
对书包有三种情况

1.  书包此时容量 放不下这个物品
2.  书包容量够了，放
3.  书包容量够了，不放  
    背包的每种体积 都 对应 了这三种状态

假设 遍历完之后

dp\[n\]\[V\]就是 前n个物品，体积V时 的最优解  
我们在退回去。

1.  书包此时容量 放不下这个物品， dp\[n\]\[V\] = dp\[n-1\]\[V\]，这个dp\[n-1\]\[V\]由于之前遍历已经得出值了，所以 可以倒着退回去，得到每个物品是否放入书包
2.  书包容量够了，放
3.  书包容量够了，不放

#include <iostream>
    #include <cstdlib>
    
    using namespace std;
    const int MAXN = 30 + 5;
    const int MAXV = 2e4 + 5;
    
    int dp[MAXN][MAXV];
    int main()
    {
        
        ios::sync_with_stdio(false);
        int V, n;
        cin >> V >> n;
        for (int i = 1; i <= n; i++)
        {
        
            int weight_of_this_goods;
            cin >> weight_of_this_goods;
            for (int j = 1; j <= V; j++)
            {
        
                if (weight_of_this_goods > j)
                    dp[i][j] = dp[i-1][j];
                else 
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight_of_this_goods] + weight_of_this_goods);
            }
        }
        cout << V - dp[n][V]  << endl;
        system("pause");
        return 0;
    }