2018/12/11 zhoulian 6 - h

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

int n;
int pri[1200];
int m;               // 第一种情况
int cnt=0;          // 数组下标
int sum=0;         // 菜的总价
int k=0;            // k= m-5 ;
int mm;           // 第二种情况
int mmm=99999;          // 第三种情况
char vis[1200];            // 'Y'为取，'N'为不取

int GetRes(void){
    int p=0;   //  当前数组下标
    int temp=0;    // 当前子集合
    while(p >= 0){
        if('N' == vis[p]){
            //选中当前项
            vis[p] = 'Y';
            temp+=pri[p];
            if(temp == k){
                return 1;
            }
            else if(temp > k){
                vis[p] = 'N';         //重置
                temp-=pri[p];
            }
            p++;
        }
        if(p >= n){
            while('Y' == vis[p-1]){
                p--;
                vis[p]='N';
                temp-=pri[p];
                if(p < 1){
                    return 0;
                }
            }
            while('N' == vis[p-1]){
                p--;
                if(p < 1){
                    return 0;
                }
            }
            vis[p-1] = 'N';
            temp-=pri[p-1];
        }
    }
    return 0;
}

int main()
{

    while(1){        //输入菜的数量
        scanf("%d",&n);
        if(n==0){
            break;
        }
        cnt=0;
        sum=0;
        mmm=99999;                        //初始化

        memset(pri,0,sizeof(pri));
        memset(vis,0,sizeof(vis));

        for(int i = 0 ; i < n ; i++){
            scanf("%d",&pri[i]);     // 输入每个菜的价格
            vis[i]='N';
            sum+=pri[i];
        }
        scanf("%d",&m);            // 输入卡的余额
        mm=m;
        k=m-5;

        if(m<5){                       //情况1
            printf("%d\n",m);
            continue;
        }

        if(sum<m){                 // 情况2
            printf("%d\n",m-sum);
            continue;                  //输出 结束本次循环
        }

        sort(pri,pri+n);          //从小到大排好
        if(GetRes()){              
         //  情况3 (如果 pri[]中 能有数相加== k  ，那么就是5 - pri[]中最大的
        //   得到的结果最小) 
            mmm=5-pri[n-1];
        }
        for(int i = n-2 ; i >= 0 ; i--){           // 从大到小 减
            if(k-pri[i]>=0){
                k-=pri[i];
            }
        }
        m = k+5-pri[n-1];

        for(int i = 0 ; i < n-1 ;i++){        // 从小到大  减
            if(mm-pri[i]>=5){
                mm-=pri[i];
            }
        }
        mm=mm-pri[n-1];
        m=min(mm,m);
        m=min(mmm,m);                     //取最小

        printf("%d\n",m);

    }


    return 0;
}

 

 

 在一个数组中任意个数 之和 等于 给定的数  ， 输出数组中这几个数 ( 输出的是一种情况) 

 

#include <iostream>
using namespace std;
#include <stdio.h>
int len;
int sum;
int data[100000]; // 数据.
char output[100000]; // 所求子集元素，与输入数据对应，'Y'为取.‘N’为不取
void GetInput(){
    int i;
    cin >> len >> sum ;
    for(i = 0; i < len; i++){
        scanf("%d", &data[i]);
        output[i] = 'N';
    }
}
int GetRes(){
    int p = 0; // 指向当前值.
    int temp = 0; // 当前子集合和.
    while(p >= 0){
        if('N' == output[p]){
            // 选中当前项.
            output[p] = 'Y';
            temp += data[p];
            if(temp == sum){
                return 1;
            }
            else if(temp > sum){
                output[p] = 'N';
                temp -= data[p];
            }
            p++;
        }
        if(p >= len){
            while('Y' == output[p-1]){
                p--;
                output[p] = 'N';
                temp -= data[p];
                if(p < 1){
                    return 0;
                }
            }
            while('N' == output[p-1]){
                p--;
                if(p < 1){
                    return 0;
                }
            }
            output[p-1] = 'N';
            temp -= data[p-1];
        }
    }
    return 0;
}
void PrintRes(){
    int i ;
    for(i = 0; i < len; i++)
    {
        if('Y' == output[i])
        {
            // best[k]=data[i];
            cout<<data[i]<<" ";
            // k++;
        }
    }
    cout<<endl;
    // for( i = 0 ; i < k-1 ; i ++ )
    //cout << best[i] << " ";
    //cout<<best[i]<<endl;
}
int main()
{
    GetInput();
    if(GetRes())
    {
        PrintRes();
    }
    else
    {
        cout<<"No Solution!"<<endl;
    }
    return 0;
}

（回溯法：遇到合适的就取，取到后面的时候满足不了，就后退，重新取下一个满足的）：

 输入：数组长度 定值

数组中的数

例如：5 10
 4 5 2 6 2
输出 ： 4 6