01 背包【题目描述】 这是一个so easy的问题：你有一个容量为M的背包。你希望将N个物品放入背包，每个物品

Question

【题目描述】
这是一个so easy的问题：你有一个容量为M的背包。你希望将N个物品放入背包，每个物品的体积是Vi，价值是Wi。显然，并非所有物品都可以放入背包。那么，怎样放才能在不超过总体积的情况下，使所放物品价值最大？
请你编程解决这个问题。同时，请你求出，有多少种不同的放法可以达到最大价值。注意，输入的物品各不相同。尽管某些物品的价值和体积可能相等，但它们不属于同一物品。
【输入文件】
第一行两个整数N,M
接下来n行，每行两个整数Vi,Wi
【输出文件】
共两行，第一行一个整数表示最大价值。第二行一个整数表示最优放法数量。
【输入样例】
3 4
2 2
2 1
3 3
【输出样例】
3
2
【样例说明】
你可以放前两个物品，总价值3。也可以只放第三个物品，总价值也为3。
【数据规模和约定】
对于10%的数据，n<=10
对于100%的数据，n,m<=1000，Vi,Wi<=1000
对于每个测试点，如果你的两个答案都正确，得10分；只有第一个答案正确，得4分；否则不得分。

Answer 1

#include<stdio.h>
#include<conio.h>

#define max 100

int n=0,mon[max]={0},hev[max]={0},hmax=0;
int nowh=0,nowm=0;
int mmax=0;
int as[max]={0};
int asmax[max]={0};
int stmax=0;
int st=-1;
void print();
void fun(int p);
void print()
{
printf("有以下物品\n");
for(int i=0;i<stmax+1;i++)
printf("物品%d ",asmax[i]+1);
printf("一共价值为:%d",mmax);
}

void fun(int p)
{
if(p==n)
{
if(nowm>=mmax)
{
for(int i=0;i<st+1;i++)
asmax[i]=as[i];
stmax=st;
mmax=nowm;
}return;
}
if(nowh+hev[p]<=hmax)
{
fun(p+1);
st++;
as[st]=p;
nowh+=hev[p];
nowm+=mon[p];
fun(p+1);
nowh-=hev[p];
nowm-=mon[p];
st--;
}
else
fun(p+1);
}

int main()
{
printf("求解背包问题\n");
printf("请用户输入物品数量：");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("第%d个物品的价钱:",i+1);
scanf("%d",&mon[i]);
printf("第%d个物品的体积:",i+1);
scanf("%d",&hev[i]);
printf("\n");
}
printf("请输入体积限制:");
scanf("%d",&hmax);
fun(0);
print();
_getch();
return 0;
}本回答被网友采纳