“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S

动态规划求一组解，我们用f[i][j]用来表示前i件物品随意选择一些物品能够恰好装满容量为j的背包的可行性=1，不可行则为0；如果j < v[i]:f[i][j] = f[i-1][j] ，表示第i个物品的重量已经超过最大重量j了，则结果变为了前i-1件物品能否恰好装入容量为j的背包的可行性即等于f[i-1][j]；

如果j>=v[i]，此时就可以选择装或者不装第i件物品了，如果装入，则它的可行性就变为了前i-1前物品是否能恰好装入j-vec[i]容量的背包中可行性了；选择不装，则它的可行性变为了前i-1物品能否恰好装入容量为j的背包中可行性了，两者有一个可行，表明前i件物品就能恰好装入容量为j的背包中。f[i][j] = f[i-1][j]||f[i-1][j-vec[i]]

初始化：f[i][0]=1(i=0,1,2,,..n) 其它的f[i][j]都等于0

void packageInteration(vector<int> vec, int S){
    int n = vec.size();
    int **f = new int*[n+1];
    for(int i = 0; i < n+1; i++){
        f[i] = new int[S+1];
        memset(f[i], 0, sizeof(f[i])*(S+1));
    }
    for(int i = 0; i < n+1; i++)
        f[i][0] = 1;   // 初始化
    for(int i = 1; i < n+1; i++){
        for(int j = 1; j < S+1; j++){
            if(j >= vec[i-1])
                f[i][j] = (f[i-1][j] || f[i-1][j-vec[i-1]]);
            else
                 f[i][j] = f[i-1][j];
        }    
    }
    // 回溯求结果
    int j = S;
    for(int i = n; i > 0; i--){
        if(j >= vec[i-1]){
            if(f[i][j-vec[i-1]] == 1){   // 为1 表示可行
                res.push_back(i);
                j = j - vec[i-1];
            }
        }
    }
}

	/**
	 * 将子集和问题转化为0-1背包问题
	 * dp[i][j]的含义：承重为j的背包中的前i个物品中最有价值子集的总价值
	 * 递推关系：
	 * j-arr[i]>=0,dp[i][j] = max{dp[i-1][j],arr[i] + dp[i-1][j-arr[i]]};
	 * j-arr[i]< 0,dp[i][j] = dp[i-1][j]。
	 */
	public LinkedList<Integer> SubSetSum2(int[] arr, int s) {
		LinkedList<Integer> res = new LinkedList<Integer>();
		if (arr == null || arr.length == 0 || s < 0)
			return res;
		int dp[][] = new int[arr.length+1][s + 1];
		// 计算第一行：当背包中没有物品时，总价值为0，这一步可通过dp初始化时默认为0来完成。
		// 计算其他行
		int i,j;
		for (i = 1; i < arr.length+1; i++) {
			for (j = 0; j < s+1; j++) {
				if(j-arr[i-1]>=0){
					dp[i][j] = Math.max(dp[i-1][j],arr[i-1] + dp[i-1][j-arr[i-1]]);
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		if(dp[arr.length][s]<s)
			return res;// 表示不存在和为s的子集
		// 通过回溯动态规划表，找出和为s的一个子集
		i = arr.length;
		j = s;
		while (j >= 0 && i >= 1) {
			if (dp[i][j]>dp[i - 1][j]) {
				res.addFirst(arr[i-1]);
				j -= arr[i-1];
			}
			i--;
		}
		return res;
	}

	/**
	 * dp[i][j]的含义：
	 * 1.是否存在arr[0...i-1]的子集，使得子集和为j，若存在为true，不存为false。
	 * 2.当dp[i-1][j]为true时，dp[i][j]以及dp[i][j+arr[i]]必然也为true（当然，j+arr[i]不能越界）。
	 */
	public LinkedList<Integer> SubSetSum(int[] arr, int s) {
		LinkedList<Integer> res = new LinkedList<Integer>();
		if (arr == null || arr.length == 0 || s < 0)
			return res;
		boolean dp[][] = new boolean[arr.length][s + 1];
		int i, j;
		// 构造第一行
		for (i = 0; i < s + 1; i++) {
			if (i == arr[0])
				dp[0][i] = true;
			dp[0][0] = true;
		}
		// 构造其他行
		for (i = 1; i < arr.length; i++) {
			for (j = 0; j < s + 1; j++) {
				if (dp[i - 1][j]) {
					dp[i][j] = true;
					if (j + arr[i] <= s)
						dp[i][j + arr[i]] = true;
				}
			}
		}
		if(!dp[arr.length-1][s])// 表示不存在和为s的子集，直接返回
			return res;
		// 通过回溯动态规划表，找出和为s的一个子集
		i = arr.length - 1;
		j = s;
		while (j >= 0 && i >= 1) {
			if (!(dp[i][j] && dp[i - 1][j])) {
				res.addFirst(arr[i]);
				j -= arr[i];
			}
			i--;
		}
		if (j == arr[0])
			res.addFirst(arr[i]);
		return res;
	}

/*

public static int[] returnValuesAddToVolume(int[] values,int volume)
	{
		boolean[][] stat = new boolean[values.length+1][volume+1];
		stat[0][0]=true;//stat[][]就是上面的F[][]
		for(int i=1;i<values.length+1;i++)
		{
			for(int j=0;j<volume+1;j++)
			{
				if(j<values[i-1])
				{
					stat[i][j]=stat[i-1][j];
				}
				else
				{
					stat[i][j]=stat[i-1][j] || stat[i-1][j-values[i-1]];
				}
			}
		}
		if(stat[stat.length-1][stat[0].length-1])//这表示有解
		{
			int i = values.length;
			int j = volume;
			List<Integer> list = new ArrayList<Integer>();
			while(i>0 && j>0)
			{
				if(j>=values[i-1] && stat[i][j]==stat[i-1][j-values[i-1]])
				{
					list.add(values[i-1]);
					j=j-values[i-1];
				}
				i--;
			}
			Integer[] temp = list.toArray(new Integer[list.size()]);
			int[] result = new int[temp.length];
			for(int k=0;k<result.length;k++)
			{
				result[k]=temp[k].intValue();
			}
			return result;
		}
		else
		{
			int[] result = {-1};
			return result;
		}
	}

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX_OBJS   10
#define MAX_WEIGHT 40

int obj_weight[MAX_OBJS] = {3, 9,  10, 1,  3, 4,  8, 12, 11, 22};
int obj_value[MAX_OBJS] =  {8, 11, 23, 19, 1, 44, 2, 4,  1,  23};

int v_array[MAX_OBJS+1][MAX_WEIGHT+1];
int r_array[MAX_OBJS+1][MAX_WEIGHT+1];

int find_solution_none_recursive(int n, int w)
{
    int i, j;
    int nSolution1 = 0;
    int nSolution2 = 0;

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= w; j++)
        {
            nSolution1 = 0;
            nSolution2 = 0;

            if (obj_weight[i-1] <= j)
            {
                nSolution1 = v_array[i-1][j-obj_weight[i-1]] + obj_value[i-1];
            }
            nSolution2 = v_array[i-1][j];

            if (nSolution1 > nSolution2)
            {
                r_array[i][j] = 1;
                v_array[i][j] = nSolution1;
            }
            else
            {
                v_array[i][j] = nSolution2;
            }
        }
    }

    return v_array[n][w];
}

void print_solution(int n, int w)
{
    if (n < 0)
    {
        return;
    }

    if (r_array[n][w] == 1)
    {
        print_solution(n-1, w-obj_weight[n-1]);
        printf("obj[%d]: weight: %-20d value: %-20d\n", n, obj_weight[n-1], obj_value[n-1]);
    }
    else
    {
        print_solution(n-1, w);
    }
}

void main(void)
{
    int max_v = 0;
    memset(r_array, 0, sizeof(r_array));
    memset(v_array, 0, sizeof(v_array));

    //max_v = find_solution_recursive(MAX_OBJS, MAX_WEIGHT);

    max_v = find_solution_none_recursive(MAX_OBJS, MAX_WEIGHT);
    printf ("max_v = %d\n", max_v);
    print_solution(MAX_OBJS, MAX_WEIGHT);
}

#include <iostream>
using namespace std;
int main()
{
    int k = 1, a[1000], b[1000], w, p, price[1000], weight[1000], m, c, i, j, v = 0;
    cout << "请输入物品个数" << endl;
    cin >> m;
    cout << "请输入背包总容量" << endl;
    cin >> c;
    cout << "请输入每个物品的重量" << endl;
    for ( i = 1; i <= m; i++ )
        cin >> weight[i];
    cout << "请输入每个物品的价值" << endl;
    for ( i = 1; i <= m; i++ )
        cin >> price[i];
    for ( i = 0; i <= m; i++ )
        a[i] = 0;
    while ( k >= 1 )
    {
        a[k] += 1;

        if ( a[k] <= 2 && k == m )
        {
            w   = 0;
            p   = 0;
            for ( i = 1; i <= m; i++ )
            {
                if ( a[i] == 1 )
                {
                    w   = w + weight[i];
                    p   = p + price[i];
                }
            }
            if ( w <= c && p > v )
            {
                v = p;
                for ( j = 1; j <= m; j++ )
                {
                    if ( a[j] == 2 )
                    {
                        b[j] = 0;
                    }else  {
                        b[j] = a[j];
                    }
                }
            }
        }
        if ( a[k] <= 2 && k < m )
            k++;
        else{
            a[k] = 0;
            k--;
        }
    }
    cout << endl;
    cout << "应放入";
    for ( i = 1; i < m; ++i )
        if ( b[i] == 1 )
            cout << i << ",";
    cout << b[m];
    cout << "号物品" << endl;
    cout << "最大价值为" << v << endl;
    system( "pause" );
    return(0);
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MAXN  20
#define MAXW   100
void Backage(int W[],int n,int MaxS){
    bool dp[MAXN][MAXW]; //标记选中k件物品的重量为s是否存在
    memset(&(dp[0][0]),0,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=i;j>=1;j--){
            for(int s=1;s<=MAXS;s++){
                if(s>=W[j-1]&&dp[i][s-S[j-1]])
                     dp[i][j]=true;
            }
        }
    }
    
}
int main(){


    return 0;
}

#include<iostream> using namespace std; int f[1000], w[1000], v[1000];
int pre[1000];
void PrtSolution(int i ) {
    int j = i;
    while(j!=0) {
         cout<<j - pre[j] << " ";
         j = pre[j];
    }
} int main() {  cin>>S;
    f[0] = 1;
    for(int i = 1;i<=0;i++) 
        for(int i = S; i>=w[i]; i--) {
            if(f[i - w[i]] == 1) {
                    f[i] = 1;
                    pre[i] = i-w[i];
         }      
    if(f[i] == 1) {
          PrtSolution(i);
    }
} 

//腾讯2014研发笔试题
/*
“背包题目”的基本描述是：有一个背包，能盛放的物品总重量为S,设有N件物品，其重量分别为w1，w2，…，wn，希望从N件物品中选择若干物品，所选物品的重量之和恰能放进该背包，即所选物品的重量之和即是S。递归和非递归解法都能求得“背包题目”的一组解，试写出“背包题目”的非递归解法
*/

#include<iostream>
#include<math.h>
using namespace std;

#define GOODS_QUANTITY 4
#define BAG_ALLOWABLE_WEIGHT 7

//背包类
class BAG
{
public:
	BAG(int allowable_weight)
	{
		this->allowable_weight=allowable_weight;
	}

	int get_allowable_weight()
	{
		return allowable_weight;
	}

	void print_allowable_weight()
	{
		cout<<"allowable weight of bag: "<<allowable_weight<<endl;
	}

private:
	int allowable_weight;
};

//物品类
class GOODS
{
public:
	GOODS(int weight)
	{
		this->weight=weight;
	}

	GOODS()
	{
		weight=0;	
	}

	void set_weight(int weight)
	{
		this->weight=weight;
	}

	int get_weight()
	{
		return weight;
	}

	void print_weight()
	{
		cout<<weight<<' ';
	}	

private:
	int weight;
};

//打印解
void print_answer(BAG &bag,GOODS *goods_ptr,int goods_quantity);

int main()
{
	int i;	
	
	//初始化测试用例
	BAG bag(BAG_ALLOWABLE_WEIGHT);
	bag.print_allowable_weight();	
	GOODS goods_set[GOODS_QUANTITY];
	cout<<"goods weight: "<<endl;
	for(i=1;i<=GOODS_QUANTITY;i++)
	{
		goods_set[i-1].set_weight(i);
		goods_set[i-1].print_weight();
	}
	cout<<endl;
	
	//计算结果
	print_answer(bag,goods_set,GOODS_QUANTITY);

	return 0;
}

void print_answer(BAG &bag,GOODS *goods_ptr,int goods_quantity)
{
	int i,j;
	int sum;
	bool mask[goods_quantity];

	for(i=0;i<goods_quantity;i++)
	{
		mask[i]=false;
	}

	cout<<"answer:"<<endl;

	//模拟二进制数递增过程，并以mask数组为掩码获得所有组合并判断是否为解
	for(i=0;i<pow(2,goods_quantity)-1;i++)
	{
		//生成一组掩码		
		j=0;
		while(j<goods_quantity)
		{
			if(mask[j]==true)
				mask[j]=false;
			else
			{
				mask[j]=true;
				break;
			}
			j++;
		}

		//使用掩码取得一组组合并求出质量之和
		sum=0;
		for(j=0;j<goods_quantity;j++)
		{
			if(mask[j]==true)
			{
				sum+=(goods_ptr+j)->get_weight();
			}
		}

		//为解则打印出结果
		if(sum==bag.get_allowable_weight())
		{
			for(j=0;j<goods_quantity;j++)
			{
				if(mask[j]==true)
				{
					(goods_ptr+j)->print_weight();
				}
			}
			cout<<endl;
		}
	}
}

/*
问题的解决方案：
DP: bool flag[N][S]表示包含前N个物品中的若干个，背包重量为S的可行性
	则 flag[N+1][S] = flag[N][S] || flag[N][S-w[N+1]];
	再用一个chosen来标记是否有物品被选中
*/

bool Packing(int S, int *w, int N, int *resset, int& resLen) {
	resLen = 0;
	bool ret = false;
	bool **flag = new bool*[N];
	bool **chosen = new bool*[N];
	for (int i = 0; i < N; i++) {
		flag[i] = new bool[S + 1];
		chosen[i] = new bool[S + 1];
	}
	flag[0][0] = true;
	for (int s = 1; s <= S; s++)
		flag[0][s] = (s == w[0]);
	for (int n = 1; n < N; n++) {
		flag[n][0] = true;
		for (int s = 1; s <= S; s++) {
			if (s >= w[n]) {
				if (flag[n - 1][s - w[n]]) {
					flag[n][s] = true;
					chosen[n][s] = true;
				}
				else {
					flag[n][s] = flag[n - 1][s];
					chosen[n][s] = false;
				}
			}
			else {
				flag[n][s] = flag[n - 1][s];
				chosen[n][s] = false;
			}
		}
	}
	for (int n = 0; n < N; n++) {
		if (flag[n][S]) ret = true;
	}
	if (ret) {
		int left = S;
		int leftN = N - 1;
		while (left > 0) {
			for (int n = leftN; n >= 0; n--) {
				if (chosen[n][left]) {
					left -= w[n];
					leftN = n - 1;
					resset[resLen++] = n;
					break;
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		delete[] flag[i];
		delete[] chosen[i];
	}
	delete[] flag;
	delete[] chosen;
	return ret;
}

//动态规划解法：status[i][j]表示能否从1-i中选择若干其重量和为j
//status[itemNum][S]为true表示问题有解，再通过回溯输出结果
#include <iostream>

using namespace std;

const int MAX_ITEM_NUM = 10;
const int MAX_TOTAL_WEIGHT = 10000;
int weights[MAX_ITEM_NUM];
bool status[MAX_ITEM_NUM][MAX_TOTAL_WEIGHT];
int S;
int itemNum;

int main()
{
	cin >> S;
	cin >> itemNum;
	for(int i=1; i<=itemNum; ++i)
	{
		cin >> weights[i];
	}

	for(int i=0; i<=itemNum; ++i)
	{
		status[i][0] = true;
	}

	for(int i=1; i<=itemNum; ++i)
	{
		for(int j=0; j<=S; ++j)
		{
			if(weights[i] > j)
			{
				status[i][j] = status[i-1][j];
			}
			else
			{
				status[i][j] = (status[i-1][j] || status[i-1][j-weights[i]]);
			}
		}//for(j)
	}//for(i)

	if(status[itemNum][S])
	{
		int tmpS = S;
		for(int i=itemNum-1; i>=0; --i)//回溯一个输出结果
		{
			if(status[i][tmpS-weights[i+1]])// status[i][tmpS-weights[i+1]]为真说明可以从1-i中找若干使其等于tmpS-weights[i+1]，所以我们就可以选第i+1项
			{
				cout << weights[i+1] << " ";
				tmpS -= weights[i+1];
			}
		}
		cout << endl;
	}
	else
	{
		cout << "no " << endl;
	}

	system("pause");
	return 0;
}