提示：本文例题为 HDU 2602
    这次写博客其实也是一次为了纪念吧。背包的第一题就出师不利拿到题目后身边小伙伴一个接一个交题，就我连测试数据都过不去，直到第二天才交过，心里面很是不爽= =#
    不过好在交过了对吧？反正就是对了，然后也代表第一个简单的栗子学会了，这里也分享一下吧。
    0-1背包的意思呢，地上放了一大堆东西，你开始往一个大小固定的包里面装，人嘛，总是贪婪的，所以你要做到包里面装的东西价值最高，已知包的容量和各个物品的体积，价值，以及各个物品的数量。
    现在，求解。
   第一眼看到这个东西没有经过任何讲解，没看过任何资料的话几乎百分之百肯定是要懵逼的，人为去尝试的话就只会穷举法，循环数量肯定超，况且数量一大就忙不过来了，这次我们先采用dp（动态规划）来解决这道问题。
    首先我们假设有5个物品，背包容量为10。五个物品体积分别为1，2，3，4，5。价值为5，4，3，2，1。那么现在我们直接给思路：
    然后我们假设，有11个包（思考一下为什么不是10个），容量分别为0，1，2，3，4，5，6，7，8，9，10。（容量为0的可以认为包漏了，丢了，或者怎样都行别让它装东西）。
   然后开始求解，步骤是，物品从前向后遍历（不考虑物品摆放的顺序），每个物品再遍历一遍你的六个包，看看减去这个物品体积时包里面装的东西价值是多少，加上现在这个物品的价值是否超过包的容量，以及价值是否比原来的高，如果即不超过容量，价值又高，就可以放进去。
    你会发现这样的话每个物品过后，对应背包容量的最优解就更新了。
    如此循环，遍历物品结束后就会发现，最大的容量包就是我们要求解的答案，因为每次遍历背包的时候都是现在要放这件物品时所有背包容量的最优解，所以，最后最优解就很简单就出来了。
    这里给出上面那题的示例代码（变量名字有点复杂不过还好）:
    
/*一维数组解0-1背包代码，题目：hdu2602*/
#include<stdio.h>
#include<string.h>
int ValueOfBone[1010], VolumeOfStone[1010];//骨头价值和体积分开存储，对应的位置相对应
int KindsOfBag[1010];//用来看背包容量不同的时候的最优解
int main()
{
	int t;//测试数据组数
	int NumberOfBone, VolumeOfBag;//骨头数量和体积
	scanf("%d", &t);
	while (t--)
	{
		memset(ValueOfBone, 0, sizeof(ValueOfBone));
		memset(VolumeOfStone, 0, sizeof(VolumeOfStone));
		memset(KindsOfBag, 0, sizeof(KindsOfBag));//三个数组均初始化
		scanf("%d %d", &NumberOfBone, &VolumeOfBag);
		for (int i = 0; i < NumberOfBone; i++)//按照题目要求输入骨头对应的价值
		{
			scanf("%d", &ValueOfBone[i]);
		}
		for (int i = 0; i < NumberOfBone; i++)//然后是体积
		{
			scanf("%d", &VolumeOfStone[i]);
		}
		for (int i = 0; i < NumberOfBone; i++)//下面开始dp！从第一根骨头向后遍历看各个骨头
		{
			for (int j = VolumeOfBag; j >= VolumeOfStone[i]; j--)//从后向前遍历背包不同容量时的最优解（从前向后的话容易解错）
			{
				KindsOfBag[j] = (KindsOfBag[j] >= KindsOfBag[j - VolumeOfStone[i]] + ValueOfBone[i] ? KindsOfBag[j] : KindsOfBag[j - VolumeOfStone[i]] + ValueOfBone[i]);//状态转移方程！
			}
		}
		printf("%d\n", KindsOfBag[VolumeOfBag]);//输出最后的最优解
	}
	return 0;//结束程序
}

题目链接：点击打开链接
题意：
地上有n个背包，编号从1-n
下面n行第i行： 第一个数字表示背包i里有几个背包。
这样就得到了n个背包的一个状态。


问：有多少个背包状态可以通过一系列的操作达到输入的状态。
每步操作：
选取一个在地面上的背包a，然后把a背包内部的背包放到地上，把地上的放到a背包内部


思路：
我们可以把背包的嵌套关系 用一个图来表示。
就得到了一个森林，然后以地面为根把所有在地上的包相连，就得到了一棵树。
那么对于每次操作相当于换根操作。
所以一共有n-1个方法可以把根移动到其他地方。（画图模拟一下）
（1个背包时要特判）


#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
	int n, x, y;
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &x);
			while (x -- > 0) {
				scanf("%d", &y);
			}
		}
		if (n == 1)
			puts("1");
		else
			printf("%d\n", n + 1);
	}
	return 0;
}

给出G种宝石，B个包，和S，S代表到时候每种颜色的宝石凑齐S个能变成一个魔法石
每个包里有N种宝石，分别为c1，c2.......
然后两人轮流拿包，每个包只能拿一次，拿出包把宝石放地上。

如果能变成魔法石则拿走魔法石，下一次还这个人拿包，没变成则换人。

魔法石的个数就是获得分数，问两人最优的时候分差是多少。



状压记忆化搜索
一共21个包，状压存当前取包的状态
无论怎样取，最后获得的魔法石数量一定
dp[i]表示在i状态下，先手可以获得的最高分数


#include "stdio.h"
#include "string.h"

int aim,g,b,s;
int dp[1<<22],c[25][10];
int bit[25];
int inf=0x3f3f3f3f;

int Max(int a,int b)
{
    if (a<b)return b;
    else return a;
}
int dfs(int cur,int sum,int temp[])
{
    int ans,i,next,j,w,cnt;
    int mark[10];
    if (cur==aim || sum==0) return 0;
    if (dp[cur]!=inf) return dp[cur];

    ans=0;
    for (i=1;i<=b;i++)
        if (cur&bit[i])
        {
            next=cur^bit[i];
            cnt=0;
            for (j=1;j<=g;j++)
            {
                mark[j]=temp[j]+c[i][j];
                cnt+=mark[j]/s;
                mark[j]%=s;
            }
            if (cnt>0) w=cnt+dfs(next,sum-cnt,mark);
            else w=sum-dfs(next,sum,mark);
            ans=Max(ans,w);
        }
    return dp[cur]=ans;
}
int main()
{
    int i,n,x,sum,aim,ans;
    int all[10],mark[25];
    bit[1]=1;
    for (i=2;i<=22;i++)
        bit[i]=bit[i-1]*2;

    while (scanf("%d%d%d",&g,&b,&s)!=EOF)
    {
        if (g+b+s==0) break;
        memset(c,0,sizeof(c));
        memset(all,0,sizeof(all));
        for (i=1;i<=b;i++)
        {
            scanf("%d",&n);
            while (n--)
            {
                scanf("%d",&x);
                c[i][x]++;
                all[x]++;
            }
        }
        sum=0;
        for (i=1;i<=g;i++)
            sum+=all[i]/s;

        aim=bit[b+1]-1;
        memset(mark,0,sizeof(mark));
        memset(dp,inf,sizeof(dp));
        ans=dfs(0,0,mark);
        printf("%d\n",ans-(sum-ans));
    }
    return 0;
}

? DebugSpawn"XX"——放一个XX在鼠标指针指示的地上
? c_give(“XX”,数量)——直接放包里
? c_spawn(“XX”，数量)——放鼠标指针指示的地上
转载于:https://www.cnblogs.com/xucanhu/p/10242999.html