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

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;
        }
}

#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;
}