x.cpp

背包问题的解决 :给定一个超递增序列和一个背包的容量,然后在超递增序列中选(只能选一次)或不选每一个数值,使得选中...解决0/1背包问题的方法有多种,最常用的有贪婪法和动态规划法。

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

int T,n;
int *w,*used;

void knap(int start,int sum)
{   int i;
	if(sum > T) return;
    else if(sum == T)
    {   for(i=0;i<n;++i)
            if(used[i])printf("%4d",w[i]);
        printf("\n");
        return;
    }
    if(start == n)return;
    used[start] = 1;
    knap(start+1,sum+w[start]);
    used[start] = 0;
    knap(start+1,sum);
}

void main()
{
    int i;
	printf("输入需达到的总重量 T = ");/*输入T*/
    scanf("%d",&T);
	printf("输入物品件数 n = ");/*输入n*/
    scanf("%d", &n);
    w = (int *)malloc(n*sizeof(int));    //存储各物品重量的数组
    used = (int *)malloc(n*sizeof(int)); //存储各物品被使用的状况
	printf("输入每件物品重量 %d (weight):\n", n);/*输入重量*/
    for(i=0;i<n;++i)
    {   scanf("%d",w+i);
        used[i] = 0;
    }
    knap(0,0);
    free(used);
    free(w);
}