Question

求动态规划01背包问题c语言的代码，要稍微简单且无错的。谢谢

Answer 1

int c[10][100];/*对应每种情况的最大价值*/

int knapsack(int m,int n){ // 一个载重为m的背包 总共n个物品
int i,j,w[10],p[10];
printf("each weight & value ：\n");
for(i=1;i<=n;i++)
scanf("%d %d",&w[i],&p[i]); // 第i个 物品的重量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;i++) //遍历每一个物品i
for(j=1;j<=m;j++) //假设背包的载重j为1、2、3、4、5、... ... m的情况
{
if(j >= w[i]) /*如果当前物品的重量 < 背包载重*/
{
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];
// c[i][j] = (p[i]+c[i-1][j-w[i]]>c[i-1][j])?(p[i]+c[i-1][j-w[i]]):(c[i-1][j]);
}
else c[i][j]=c[i-1][j];
}
return c[n][m];

}

int main()
{
int m,n;
printf("背包的承重量,物品的总个数：\n");
while(scanf("%d %d",&m,&n) != EOF){
printf("能装的最大总价值为%d",knapsack(m,n));
printf("\n");
}
return 0;
}

Answer 2

我写个C++的。

#include<iostream>
#define MAX 1111
using namespace std;
int f[MAX],n,m,v,w;
int main(){
cin>>n>>m;//n表示个数，m表示背包容量
for(int i=1;i<=n;++i){
cin>>v>>w;//v=价值，w=重量
for(int j=m;j>=w;--j)
if(f[j]<f[j-w]+v)
f[j]=f[j-w]+v;
}
cout<<f[m]<<'\n';
return 0;
}

C++和C应该都差不多吧。。这个最简洁了 。顺便一句，如果要能无限放的话
for(int j=m;j>=w;--j)这一句变成for(int j=w;j<=m;++j)就行了。

追问

没有iostream怎么办

追答

#include
#define MAX 1111
int f[MAX],n,m,v,w;
int main(){
int i,j;
scanf("%d%d",&n,&m);//n表示个数，m表示背包容量
for(i=1;i=w;--j)
if(f[j]<f[j-w]+v)
f[j]=f[j-w]+v;
}
printf("%d\n",f[m]);
return 0;
}

这个是C的

Answer 3

#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
printf("请输入每个物品的重量,价值：\n");
for(i=1;i<=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;i++)
for(j=1;j<=m;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,n;int i,j;
printf("请输入背包的承重量,物品的总个数：\n");
scanf("%d,%d",&m,&n);
printf("旅行者背包能装的最大总价值为%d",knapsack(m,n));
printf("\n");
return 0;
}

Answer 4

楼上你那个不是贪婪算法么？