思路:先对n个体积进行从小到大的排序,然后枚举i作为剩余物品中体积最小为v,dp[i]为方案数(其中i为当前体积).那么可以分析对于大于i的,很显然是可以放进背包的,又因为i为剩余的物品,所以不放进去;对于大于i的物品则进行背包的可行方案的统计.然后计算{Fn[j]}之和。
AC代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define M 10000
#define max(a, b) (a > b ? a : b)

int data[M], dp[M];
int n, c;

int cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int main()
{
	//freopen("1.txt", "r", stdin);
	int i, j, k, test, sum, ans, num = 1;

	scanf("%d", &test);
	while (test--)
	{
		scanf("%d%d", &n, &c);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &data[i]);
		}
		qsort(data + 1, n, sizeof(data[1]), cmp);
		memset(dp, 0, sizeof(dp));
		for (i = 1, sum = 0, ans = 0; i <= n; i++)
		{
			memset(dp, 0, sizeof(dp));
			dp[sum] = 1;        
			for (j = i + 1; j <= n; j++)
			{
				for (k = c; k >= data[j] + sum; k--)
				{
					dp[k] += dp[k - data[j]];
				}
			}
			for (j = c; j >= max(c - data[i] + 1, 1); j--)  //c-data[i]+1 其中+1是因为下标以1开始
			{
				if (j >= sum)
				{
					ans += dp[j];
				}
			}
			sum += data[i];
		}
		printf("%d %d\n", num++, ans);
	}


	return 0;
}

• Re:此题怎么ac那么多人，讨论却那么少？？？鄙人讲讲自己思路。。。 (2) JustForU 2011-07-30 13:12:47