0/1背包問(wèn)題的最簡(jiǎn)單特殊情況，重量和價(jià)值相等。要求輸出放入了哪些物品，順序和輸入的時(shí)候相同，這樣從DP的時(shí)候從后面往前面遞推就好了。
背包問(wèn)題可以只用一個(gè)一維數(shù)組表示，這樣節(jié)省空間。
#include <stdio.h>
#include <string.h>
#define W 10005
int c[W], l[25];
bool p[25][W];
int main()
{
int w, n;
while(~scanf("%d", &w))
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &l[i]);
memset(c, 0, sizeof(c));
memset(p, 0, sizeof(p));
for(int i = n; i; i--)
for(int j = w; j >= l[i]; j--)
{
if(c[j] < c[j - l[i]] + l[i])
{
c[j] = c[j - l[i]] + l[i];
p[i][j] = 1;
}
}
for(int i = 1, j = w; i <= n; i++)
if(p[i][j])
{
printf("%d ", l[i]);
j -= l[i];
}
printf("sum:%d\n", c[w]);
}
return 0;
}