#include "stdafx.h"
int c[20][100];/*對應每種情況的最大價值*/
//int m 背包容量
//int n 背包個數
int knapsack(int m,int n)
{
int i,j,w[20],p[20];
for(i=1;i<n+1;i++)
{
printf("請輸入第(%d)個物品重量,價值:\n",i);
scanf("%d,%d",&w[i],&p[i]);
}
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化數組*/
for(i=1;i<n+1;i++)
{
for(j=1;j<m+1;j++)
{
if(w[i]<=j) /*如果當前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
{
//如果本物品的價值加上背包剩下的空間能放的物品的價值
//大于上一次選擇的最佳方案,
//則更新c[i][j]
c[i][j]=p[i]+c[i-1][j-w[i]];
}
else
{
c[i][j]=c[i-1][j];
}
}
else c[i][j]=c[i-1][j];
}
}
return(c[n][m]);
}
int main()
{
//int m 背包容量
//int n 背包個數
int m,n;
printf("請輸入背包最大承重,物品個數:\n");
scanf("%d,%d",&m,&n);
printf("最大價值:%d \r\n",knapsack(m,n));
int i,j;
m += 3;
n += 3;
for(j=0;j<m;j++)
{
printf("%02d ",j);
}
printf("\r\n");
for(j=0;j<m;j++)
{
printf("----",j);
}
printf("\r\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%02d ",c[i][j]);
if(j==m-1) printf("\n");
}
}
system("pause");
return 0;
}