算法提高课汇总

算法思路

理解题意

• 组合问题—只需考虑选择物品的集合.

• 每个物品可选数目: $0\sim 1$.

问题可抽象为$01$背包问题 .

01背包

• 限制: 物品的体积

• 目标: 剩余体积最小 <---> 选择的体积最大

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35, M = 20010;

int n, m;
int v[N];
int dp[M];

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

    for( int i = 1; i <= n; i ++ )
        for( int j = m; j >= v[i]; j -- )   
            dp[j] = max( dp[j], dp[j - v[i]] + v[i] );
    cout << m - dp[m] << endl;

    return 0;
}