首页 > 代码库 > P2507 - 【DP合集】m-knapsack

P2507 - 【DP合集】m-knapsack

2024-10-29 07:14:01   208人阅读

给出 n 个物品，第 i 个物品有重量 w i 。现在有 m 个背包，第 i 个背包的限重为 c i ，求最少用几个背 包能装下所有的物品。

Input

输入的第一行两个整数 n, m ( n ≤ 24 , m ≤ 100) 。 
接下来一行 n 个整数，描述 w ( w i ≤ 10^8 ) 。 
接下来一行 m 个整数，描述 c ( c i ≤ 10^8 ) 。

Output

输出一行一个整数，描述最少需要使用的背包数。如果没有可行的方案来装下所有物品，请输出”NIE” （不含引号）。

 

题解：O(∩_∩)O谢谢出这套题目的学长，题目出的很好，好了，对于这个题目，因为我们要选择几个信息或者说记住几个特征，既可以描述所以的状态又方便转移，显然这个题状态很直接，我们显然要记住这个序列的所有物品是否被选，还要记住，当前用了几个背包，
还要知道当前的背包还剩多少，所有可以状压一个2进制数i表示那些物品是否被选，设dp[i]表示要装下i最少要多少个背包，然后rest[i]
表示用了dp[i]个背包后还有一部分剩下的重物放在第dp[i]+1个背包的重量，那么转移就是显然的了。注意我是用记忆化搜索，如果dp[i]<n说明这个状态已经算过了，就可以直接返回了。
 
代码： 
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
using namespace std;
short dp[16777217];int use[16777217];
int wu[110],bao[110],n,m,inf;
 
void cl(){
    memset(wu,0,sizeof(wu));
    memset(bao,0,sizeof(bao));
    memset(dp,127,sizeof(dp));
    memset(use,127,sizeof(use));
    inf=use[0];
}
 
bool comp(int x,int y){
    if(x>y) return 1;
    return 0;
}
 
void dfs(int x){
    if(dp[x]<n) return;
    int q=inf,p=inf;
    for(int now=1;now<=n;now++){
        if(x&(1<<(now-1))){
            int r=x-(1<<(now-1));
            dfs(r);
            if(bao[dp[r]+1]-use[r]>=wu[now]) q=dp[r],p=use[r]+wu[now];
            else if(bao[dp[r]+1]>=wu[now]&&bao[dp[r]+2]>=wu[now]) q=dp[r]+1,p=wu[now];
            else continue;
            if(q<dp[x]) dp[x]=q,use[x]=p;
            else if(q==dp[x]&&p<use[x]) use[x]=p;
        }
    }
}
 
int main(){
    cl();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&wu[i]);
    for(int i=1;i<=m;i++) scanf("%d",&bao[i]);
    sort(wu+1,wu+n+1,comp);
    sort(bao+1,bao+m+1,comp);
    if(bao[1]<wu[1]) {printf("NIE");return 0;}
    dp[0]=use[0]=0;
    dfs((1<<n)-1);
    if(dp[(1<<n)-1]>m) printf("NIE");
    else printf("%d",dp[(1<<n)-1]+(use[(1<<n)-1]>0));
    return 0;
}

 

P2507 - 【DP合集】m-knapsack


联系
我们