Question

帮我看一下背包问题哪里错了，谢谢

求解背包问题：一个背包可装总重量 T，现有 n 个物件，其重量分别为（W1、W2、…、Wn）。问能否从这 n 个物件中挑选若干个物件放入背包中，使其总重量正好为 T ？若有解则给出全部解，否则输出无解。

#include <stdio.h>
#define N 100

int n;//物品总种数
float limitW;//限制的总重量
float w [N];//保存各个重量的数组
int occ [N];//当前解的选择

void find (int i, float tw)
{
int k;

if (tw + w [i] == limitW) {
occ [i] = 1;
for (k = 0; k < n; k ++) {
if (occ [k] == 1)
printf ("%4d", k + 1);
}
printf ("\n");
}

if (tw + w [i] < limitW) {
occ [i] = 1;
if (i < n)
find (i + 1, tw + w [i]);

}

occ [i] = 0;
if (i < n)
find (i + 1, tw + w [i]);
}

main ()
{
int k, num = 0;
float weight;
printf ("请输入物品种数:");
scanf ("%d", &n);
printf ("请输入各物品的重量:");
for (k = 0; k < n; k ++) {
scanf ("%f", &weight);
w [k] = weight;
}
printf ("请输入限制重量:");
scanf ("%f", &limitW);

for (k = 0; k < n; k ++)
occ [k] = 0;
find (0, 0.0);

system ("pause");
return 0;
}

Answer 1

#include <stdio.h>
#define N 100

int n;//物品总种数
float limitW;//限制的总重量
float w [N];//保存各个重量的数组
int occ [N];//当前解的选择

void find (int i, float tw)
{
int k;

if (tw + w [i] == limitW) {
occ [i] = 1;
for (k = 0; k < n; k ++) {
if (occ [k] == 1)
printf ("%4d", k + 1);
}
printf ("\n");
}

if (tw + w [i] < limitW) {
occ [i] = 1;
if (i < n)
find (i + 1, tw + w [i]);

}

occ [i] = 0;
if (i < n)
find (i + 1, tw + w [i]); //注意这里 你没有选择w[i]这个解 却又
} // 算了进去，应改为find（i+1，tw）；

main ()
{
int k, num = 0;
float weight;
printf ("请输入物品种数:");
scanf ("%d", &n);
printf ("请输入各物品的重量:");
for (k = 0; k < n; k ++) {
scanf ("%f", &weight);
w [k] = weight;
}
printf ("请输入限制重量:");
scanf ("%f", &limitW);

for (k = 0; k < n; k ++)
occ [k] = 0;
find (0, 0.0);

system ("pause");
return 0;
}