题解 P1049 【装箱问题】

深渊丶朗歌 · 2016-08-10 20:49:09 · 题解

可以用来练习回溯。对于每个物品，都有“装”或者“不装”两种可能。

#include <iostream>
#include <cstdio>
using namespace std;
int n,i,w;
int weight[20001]={0};//储存n个物品的重量
int cp=0,bestp=0;//cp是当前的重量，bestp是最大的重量
void backtrack(int i){//对第i个物品进行判断
    if(i>n){//如果i>n，就说明n个物品已经完全判断完
        if(cp>bestp)bestp=cp;//如果当前重量大于最大重量，替换
        return;//返回上一级
    }
    if(cp+weight[i]<=w){//装第i个物品未超过限制
        cp+=weight[i];//将第i个物品装入背包中
        backtrack(i+1);//处理第i+1个物品
        cp-=weight[i];//回溯结束之后一定要还原
    }
    backtrack(i+1);//不装或无法装进背包，则直接进入下一层
}
int main(){
    scanf("%d%d",&w,&n);
    for(i=1;i<=n;i++)scanf("%d",&weight[i]);
    backtrack(1);//从第1个物品开始回溯
    printf("%d",w-bestp);
    return 0;
}
这种算法的时间复杂度较高，当n比较大的时候回溯算法会TLE。所以当n较大时应考虑用动态规划或其它算法。