蓝桥杯算法训练VIP-装箱问题 （C++代码）

解题思路:

01背包，dp，滚动数组

注意事项:

dp数组里存放的是当前背包中的物品的总体积而不是价值

参考代码:

#include <stdio.h>
#include <iostream>
#define N 20000

using namespace std;

int v[N+2];
int dp[N+2];

int main()
{

    int n,V;

    cin >> V >> n;

    for(int i = 1;i <= n;i++)
        cin >> v[i];

    for(int i = 1;i <= n;i++)
        for(int j = V;j >= v[i];j--)
            dp[j] = (dp[j-v[i]] + v[i]) > dp[j] ? (dp[j-v[i]] + v[i]) : dp[j];

    cout << V - dp[V] << endl;

    return 0;
}