【Week11作业-F - 选做题11-2】东东开车了 UVA - 624

算法

0-1背包

题目描述

给出背包容量与N个物品；要求输出最优解背包中的物品；

解题思路

在0-1背包问题的基础上，需要输出最优解背包中的物品；
可以通过一个数组used记录：used[i]及记录了当背包容量为i时最后一件装的物品，再通过递归输出即可。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 10010;
int f[maxn];
int a[maxn];
int used[maxn];
void dfs(int x){
    if(used[x]==0)
        return;
    cout<<used[x]<<" ";
    dfs(x-used[x]);
}
int main(){
    int sum,n;
    while(cin>>sum>>n){
        memset(f,0,sizeof(f));
        memset(used,0,sizeof(used));
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
            for(int j=sum;j>=a[i];j--){
                if(f[j-a[i]]+a[i]>f[j]){
                    f[j]=f[j-a[i]]+a[i];
                    used[j]=a[i];
                }
            }
        dfs(f[sum]);
        cout<<"sum:"<<f[sum]<<endl;
    }
    return 0;
}

题目总结

如果要输出背包中物品，可使用额外数组记录。