题解 P1049 【装箱问题】

· · 题解

这是一道非常水的水题，简单的搜索

判断当前容量是否超了，超了就return，否则继续搜索 具体代码如下：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 3000 //本人喜欢用define，代码有点丑，请不要介意
using namespace std;
int v,n;//v是背包容量，n是物品数量
int a[MAXN],Max=-2147483647;//Max用来存最高容量
void dfs(int x,int y)
{
    if(x>v)//如果大于背包容量就返回
    return;
    if(x<=v&&x>Max)//更新Max
    Max=x;
    for(int i=y+1;i<=n;i++)
    dfs(x+a[i],i);//往背包里面装物品
    return;
}
int main()
{
    scanf("%d%d",&v,&n);//输入v和n
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//读入
    }
    dfs(0,0);//开始搜索，表示从零做起
    printf("%d",v-Max);
    return 0;
}

写个题解不容易，请管理员大大放过