# 1054. (算法作业5-2)机器设计

### include

using namespace std;
int n,C,m=0x3f3f,sum=0;
struct Node{
int cost,weight;
}stu[20001][4];
void bfs(int state)
{
if(state==n){
if(sum<m) m=sum;
}
else{
for(int i=1;i<=3;i++){
if(stu[state][i].cost<C){
sum+=stu[state][i].weight;
C-=stu[state][i].cost;
bfs(state+1);
sum-=stu[state][i].weight;
C+=stu[state][i].cost;
}
}
}
}
int main()
{
while(cin>>n>>C){
for(int i=0;i<n;i++){
cin>>stu[i][1].weight>>stu[i][1].cost>>stu[i][2].weight>>stu[i][2].cost>>stu[i][3].weight>>stu[i][3].cost;
}
sum=0,m=0x3f3f;
bfs(0);
cout<<m<<endl;
}
}


50×10000×3×数据组数，好像没有多大，那直接暴力递推就好了嘛

#include<bits/stdc++.h>
using namespace std;
int n,c,rst;
int dp[55][20005];
int w1,c1,w2,c2,w3,c3;
int i,j;
int main()
{
while(cin>>n>>c){
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(i=1;i<=n;++i){
cin>>w1>>c1>>w2>>c2>>w3>>c3;
for(j=c;j>=0;--j){
dp[i][j+c1]=min(dp[i][j+c1],dp[i-1][j]+w1);
dp[i][j+c2]=min(dp[i][j+c2],dp[i-1][j]+w2);
dp[i][j+c3]=min(dp[i][j+c3],dp[i-1][j]+w3);
}
}
rst=dp[n][0];
for(i=1;i<c;++i)rst=min(rst,dp[n][i]);
cout<<rst<<endl;
}
return 0;
}


#include<iostream>
using namespace std;
int n,maxc,prew,prec,rst;//prew,prec mean w,c at present
int w[55][3],c[55][3];
int i,j;
void dfs(int pos)//pos means having finishing choosing first pos components
{
if(pos==n){
rst=min(rst,prew);
}
for(int i=0;i<3;++i){
prew+=w[pos][i];
prec+=c[pos][i];
if(prew<rst&&prec<maxc)dfs(pos+1);
prew-=w[pos][i];
prec-=c[pos][i];
}
}
int main()
{
while(cin>>n>>maxc){
for(i=0;i<n;++i){
for(j=0;j<3;++j){
cin>>w[i][j]>>c[i][j];
}
}
rst=0x3f3f3f3f;
dfs(0);
cout<<rst<<endl;
}
return 0;
}