dp――背包问题（0/1背包 装箱问题）

装箱问题是0/1背包中最简单的问题

设有重量为s的背包，和n个物品重量分别为w[i]，那么s的背包最多能装多少重量的东西。

满足动态规划基本特性，重点是状态和决策如何去设定。

把s重量的背包看成是s个 0-s重量的背包集合。

逆推法：

状态boolean opt[k]表示k重量的背包是否装满 ， k属于s

决策为：if(opt[k-w[i]]) == 满 opt[k]是满的

code：

#include

int main()
{
int s,n;
int w[100];
//输入背包重量s
scanf("%d",&s);
//输入物品数量n
scanf("%d",&n);
//输入每个物品的重量
for(int a = 0; a < n ; a++)
{
scanf("%d" , &w[a]);
}
//状态转移方程
bool opt[100] = {false};
opt[0] = true;
for(int i = 0; i < n ; i++)
for(int j = s ; j >= w[i]; j--)
{ if(opt[j] == false){
if(opt[j - w[i]]){
opt[j] = true;
}
}
}

//最小剩余量
int min = 0;
if(opt[s] == false)printf("xxxx");
while(opt[s] == false){ min++;printf("xxx");s--; }
printf("重为%d的背包最小剩余为%d\n",s,min);
return 0;
}