//算法笔记上P271 01背包 BFS
#include <cstdio>
using namespace std;
const int maxn = 30;
int n,V,maxValue = 0;//V背包容量
int w[maxn],c[maxn];//w[i]--每件物品的质量 c[i]---每件物品的价值
//DFS index为当前处理的物品编号
//sumW 和 sumC 分别为当前总重量和当前的总价值
void DFS(int index,int sumW,int sumC){
if(index == n){
if(sumW <=V && sumC > maxValue) maxValue = sumC;
return ;
}
DFS(index+1,sumW,sumC);// 不选第index的物品
DFS(index+1,sumW+w[index],sumC+c[index]);//选第index的物品
}
//剪枝升级版
void DFS_2(int index,int sumW,int sumC){
if(index == n) return;
DFS(index+1,sumW,sumC);// 不选第index的物品
//只有加入第index件物品后未超过容量V，才能继续
if(sumW + w[index] <= V){
if(sumC + c[index] > maxValue) maxValue = sumC + c[index];
DFS_2(index+1,sumW+w[index],sumC+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);
DFS_2(0,0,0);
printf("%d\n",maxValue);
return 0;
}
/**
测试数据
5 8
3 5 1 2 2
4 5 2 1 3
10
*/
//算法笔记上P273 BFS
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 100;
//序列A中n个数选k个数使得和为x，最大平方和为maxSumSqu
int n,k,x,maxSumSqu = -1,A[maxn];
vector<int> temp,ans; // temp存放临时方案，ans存放平方和最大的方案
//当前处理index号整数，当前已选整数个数为nowK
// 当前已选整数之和为sum，当前已选整数平方和为sumSqu
void DFS(int index,int nowK,int sum,int sumSqu){
// cout<<index<<nowK<<sum<<sumSqu<<endl;
if(nowK == k && sum == x){ // 找到k个数的和为x
if(sumSqu > maxSumSqu){
maxSumSqu = sumSqu;
ans = temp;
}
return ;
}
//已经处理完n个数，或者超过k个数，或者和超过x，返回
if(index == n || nowK > k || sum > x) return;
temp.push_back(A[index]); // 选择index号数
DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
temp.pop_back();
//不选index号数
DFS(index+1,nowK,sum,sumSqu);
}
//若题干修改为 数字可以重复选择
void DFS_2(int index,int nowK,int sum,int sumSqu){
// cout<<index<<nowK<<sum<<sumSqu<<endl;
if(nowK == k && sum == x){ // 找到k个数的和为x
if(sumSqu > maxSumSqu){
maxSumSqu = sumSqu;
ans = temp;
}
return ;
}
//已经处理完n个数，或者超过k个数，或者和超过x，返回
if(index == n || nowK > k || sum > x) return;
temp.push_back(A[index]); // 选择index号数
DFS_2(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);//修改本行 index+1 ---- 》 index
temp.pop_back();
//不选index号数
DFS_2(index+1,nowK,sum,sumSqu);
}
int main(){
//todo 此处如何给数组直接赋值
// A = {1,2,3,4};
/*
A[0] = 1;
A[1] = 2;
A[2] = 3;
A[3] = 4;
n = 4;
k = 2;
x = 6;
DFS(0,0,0,0);
for(int i=0;i<ans.size();++i){
printf("%d ",ans.at(i));
}
*/
cout<<"demo2:"<<endl;
A[0] = 1;
A[1] = 4;
A[2] = 7;
n = 3;
k = 5;
x = 17;
DFS_2(0,0,0,0);
for(int i=0;i<ans.size();++i){
printf("%d ",ans.at(i));
}
return 0;
}
