题目描述

在n本书中选出几本书，使得所选书达到包邮条件（即总价格>m），求最少的价格

样例

4 100
20
90
60
60

110（购买前两本）

思路：可以转化为01背包问题，可以选择n本书使得总价值最高

即在总容量为sum-m下，选择几本书使得总价格最高，其中
背包容量 = sum-m 每件商品价格为w[i],每个物品的体积w[i]
转移方程：f[i][j] = max(f[i-1][j],f[i-1][j-w[i]+w[i])
最后再用商品总价格sum -所选商品价格最大值

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35, M = N * 10010;
int w[N];
int f[N][M];
int n,m;
int sum=0;

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        scanf("%d", &w[i]);
        sum+=w[i];
    }

    // printf("%d",sum-m);
    for (int i = 1; i <=n; i ++ ){
        for (int j = 1; j <= sum-m; j ++ ){
            f[i][j] = f[i-1][j];
            if(j>=w[i]){
                f[i][j] = max(f[i][j],f[i-1][j-w[i]]+w[i]);
            }
        }
    }
    printf("%d",sum-f[n][sum-m]);

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

时间复杂度

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35, M = N * 10010;
int w[N];
int n,m;
//暴力算法

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++){
        scanf("%d", &w[i]);
    }
    int res = 1e8;
    for (int i=0;i<1<<n;i++ ){
        int sum=0;
        for(int j=0;j<n;j++){
            if(i>>j &1){
                sum+=w[j]; 
            }
        }
        if(sum>=m){
          res = min(sum,res);  
        }
        // printf("%d",sum);

    }

    printf("%d",res);
}