7-3梱包問題(C言語版)

7-3梱包問題(20点)N項目の物品があると仮定し、大きさはそれぞれs 1、s 2、...、s i、...、s Nであり、ここでs iは1≦s i≦100を満たす整数である.これらの物品を容量100の箱に入れる(連番1-N)において、梱包方法は、各物品について、箱を順番にスキャンして、その物品を第一の箱に入れるのに十分なものに入れてください.この梱包プロセスをシミュレートするプログラムを書いて、各物品が存在する箱連番と、すべての物品を置くのに必要な箱の数を出力してください.入力形式:第一行に物品の個数Nを入力してください.(≦1000);2行目はN個の正の整数s i(1≦s i≦100、i番目の物品の大きさを表す).出力フォーマット:入力順に各物品の大きさとその所在する箱番号を出力し、各物品は1行を占め、最後の行は必要な箱数を出力する.
入力サンプル:8 60 70 80 90 30 40 10 20出力サンプル:60 1 70 2 80 3 90 4 30 1 40 5 10 1 20 5考え方:各配列要素(物品)をどの箱に入れるべきかを決定することが肝心です(容器)中?2番目の物品からn-1回循環し、このn-1個の物品を検出し、前の物品との和が箱の容量を満たしているかどうか、100未満であれば箱の位置に置くべきであり、満たさなければ独立して新しい箱に入れる.参考コード:

#include
#include 
int main()
{
	int n,i,j,max=0;//max         
	int a[1005];//       
	int b[1005];//       ，           （          ） 
	int pox[10005];//      
	memset(pox,-1,sizeof(pox));
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i]; 
	}
	pox[0]=0;//          0，           ，        
	for(i=1;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			if(a[i]+b[j]<=100)
			{
				b[j]=b[j]+a[i];//             
				b[i]=0;//          
				pox[i]=j;
				break; 
			}
			else
			{
				pox[i]=i;
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(pox[i]>max)
		{
			max=pox[i];
		}
	}
	for(i=0;i<n;i++)
	{
		printf("%d %d
",a[i],pox[i]+1);
	}
	printf("%d",max+1);
	return 0;
}