题解 P1049 【装箱问题】

Taurus_Lzc · 2018-09-17 12:41:11 · 题解

01背包缩水版
发现没人用递归写背包
下见代码：

#include<iostream>
using namespace std;
int n,ans=0x7f;//给ans定一个最大值
int w[31];
int dfs(int i,int v) {//i是第i个物品取与不取，v是剩下容量
    if (i>n) {
        if (v<ans) {//更新最小值
            ans=v;
        }
    }
    else {
        if (v-w[i]>=0) {
            return max(dfs(i+1,v),dfs(i+1,v-w[i])+w[i]);//背包稍加改动
        }
        return dfs(i+1,v);
    }
}
int main(){
    int v;
    cin>>v>>n;
    for (int i=1;i<=n;i++) {
        cin>>w[i];
    }
    dfs(1,v);//从第一个物品开始取，容量当然是根据题意输入的v
    cout<<ans;
    return 0;
}

有兴趣的可以去做一下【P1048】采药，可以用这个代码更改一下即可AC（数据貌似有点水）
难一点的【P2871】手链Charm Bracelet