//将所有的组合穷尽排列出来,更新某一个特征值

/*
例题:
有n件物品,每件物品的重量为w[i],价值为c[i]。
现在需要选出若干件物品放入一个容量为V的背包中,
使得在选入背包的物品重量和不超过容量V的前提下,
让背包中物品的价值之和最大,求最大价值。(1≤n≤30)

*/
#include<iostream>
using namespace std;

#define maxn 30
int n,v;
int maxvalue=0;
int w[maxn], c[maxn];

/*
函数会一直递归调用下去,只要index没有到达n,如果到达n,则说明所有物品的岔路都已经穷举完了
每次新添加一个物品,都会生成新的岔路,每个岔路有两个选择,即是否将当前物品添加到背包
递归结束,会有2^n个方案,其中满足总容量<v且价值超出历史最大价值时,更新当前最大价值
*/
void dfs(int index,int sumv,int sumvalue) {
    if(index == n) {
        if(sumv<=v&&sumvalue>maxvalue) {
            maxvalue = sumvalue;
        }
        return ;
    }
    dfs(index+1,sumv,sumvalue);
    dfs(index+1,sumv+w[index],sumvalue+c[index]);
}

/*
对上面的实现进行"剪枝"优化,即每次进行岔路选择的时候,如果添加当前物品到背包中会超出容量v
则,不添加该物品
经过优化以后,所有的岔路方案都是总容量不超出v的方案
*/
void dfs2(int index,int sumv,int sumvalue) {
    if(index == n) {
        if(sumvalue>maxvalue) {
            maxvalue = sumvalue;
        }
        return ;
    }
    dfs(index+1,sumv,sumvalue);
    if(sumv+w[index]<=v)
        dfs(index+1,sumv+w[index],sumvalue+c[index]);
}
int main() {

    scanf("%d%d",&n,&v);

    for(int i =0; i<n; i++) {
        scanf("%d",&w[i]);
    }
    for(int i =0; i<n; i++) {
        scanf("%d",&c[i]);
    }
    dfs(0,0,0);
    printf("最大价值为:%d",maxvalue);
    return 0;
}
01-02 16:38