Question

最简单的背包问题！用C++！

一个背包能装入物品的总重量为T，现有 n件物品的重量分别为w1，w2，。。。wn。编写算法从n件物品中挑选若干件恰好装满背包，即使得wi1+wi2+.....wik=T。要求找出满足条件的所有解。

Answer 1

求所有解可以用回溯法，求最优解一般用动态规划或者贪心策略。
因为题目要求所有解，故采用回溯。

先建模：
此题目等价于自然数拆分，给定一个自然数N，将N拆分成n1 + n2 + ...+ nn,使得n1 + n2 + ...+ nn = N，且n1, n2, ... nn中无重复数，求所有可能的拆分情况。这里N相当于T，n1, n2,...nn相当于w1，w2，。。。wn。建模完毕！

上代码：
#include<iostream>
using namespace std ;

// 存储可行解
int a[100] ;

// 输出一个可行解
void Output(int *a, int n)
{
for (int i = 0; i < n; i++)
cout << a[i] << " " ;
cout << endl ;
}

// 验证当前解是否可行
bool IsOk(int* a, int curIndex, int curValue)
{
for(int i = 0; i < curIndex; ++i)
if(a[i] == curValue)
return false ;
return true ;
}

// 对自然数n进行拆分，t用来控制拆分个数
void Partition(int n, int t, int *b)
{
if(n < 0)
return ;

if (n == 0) // 找到一个拆分
Output(a, t) ; //输出之
else
{
for (int i = 0; i < n; i++)
{
a[t] = b[i] ;
if(IsOk(a, t, b[i]))
Partition(n -b[i], t + 1, b) ;
}
}
}

int main(void)
{

// 拆分子数的集合，相当于各个背包党重量。可根据题目自行设定
int b[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} ;

// 背包容量为10，从b中选若干件物品，使这些物品总量为10
Partition(10, 0, b) ;

system("pause") ;
return 0 ;
}

Answer 2

#include"stdio.h"
const int N=10; //设定物体个数
const int no=2;
#define weight 10 //限制质量
#define num 100
int d[num]; //总质量
int c[num][weight]; //对应的物体位置

void Best(int a[],int n)
{
int i,j,k=0,ko=2,m;
for(i=0;i<n-1;i++) //两个物体总质量不超过限制质量所有可能
{
for(j=i+1;j<n;j++)
if((a[i]+a[j])<=weight)
{
d[k]=a[i]+a[j];
c[k][0]=i+1;c[k][1]=j+1;
k++;
}
}
int k0=0,k1=k;
while(ko) //ko是物体个数的统计，当不能再多时赋值为0，退出循环
{
for(i=k0;i<k1;i++) //多个物体总质量不超过限制质量所有可能
{
for(j=c[i][ko-1];j<n;j++)
if((d[i]+a[j])<=weight)
{
d[k]=d[i]+a[j];
for(m=0;m<ko;m++)
c[k][m]=c[i][m];
c[k][m]=j+1;
k++;
}
}if(k==k1)ko=-1; //物体个数不能再多时
k0=k1;k1=k;ko++;
}
int ok=0;
for(i=0;i<k;i++)
{
if(d[i]==weight)
{
int m=0;
while(c[i][m]!=0)
{m++;}
if(m==no)
{
m=0;
while(c[i][m]!=0)
{
printf("%d\t",a[c[i][m]-1]);
m++;ok++;
}printf("\n");
}
}

}
if(!ok) printf("No\n");
}

void main()
{
int a[N];
printf("请依次输入%d个物体的质量\n",N);
for(int i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=0;i<N;i++)
printf("物体%2d质量：%d\t",i+1,a[i]);
Best(a,N);
}

相应的字母没有完全按照你这题目来，希望你能看懂！

Answer 3

这些问题自己想想或者查一下资料再做不是比问人更好吗？