Question

01背包问题-动态规划 整理成C语言！谢谢！

#include<iostream>
#include<iomanip>
using namespace std;
int c[50][50];
int w[10],v[10];
int x[10];
int n;
void KNAPSACK_DP(int n,int W)
{
for(int k=0;k<=W;k++)
c[0][k]=0;
for(int i=1;i<=n;i++)
{
c[i][0]=0;
for(int k=1;k<=W;k++)
{
if(w[i]<=k)
{
if(v[i]+c[i-1][k-w[i]]>c[i-1][k])
c[i][k]=v[i]+c[i-1][k-w[i]];
else
c[i][k]=c[i-1][k];
}
else
c[i][k]=c[i-1][k];
}
}
}
void OUTPUT_SACK(int c[50][50],int k)
{
for(int i=n;i>=2;i--)
{
if(c[i][k]==c[i-1][k])
x[i]=0;
else
{
x[i]=1;
k=k-w[i];
}
}
x[1]=(c[1][k]?1:0);
for(int i=1;i<=n;i++)
cout<<setw(4)<<x[i];
}
void main()
{
int m;
cout<<"输入物品个数:";
cin>>n;
cout<<"依次输入物品的重量:"<<endl;
for(int i=1;i<=n;i++)
cin>>w[i];
cout<<"依次输入物品的价值:"<<endl;
for(int i=1;i<=n;i++)
cin>>v[i];
cout<<"输入背包最大容量:";
cin>>m;
for(int i=1;i<=m;i++)
cout<<setw(4)<<i;
cout<<endl;
KNAPSACK_DP(n,m);
cout<<"构造最优解过程如下:"<<endl;
for(int j=1;j<=5;j++)
{
for(int k=1;k<=m;k++)
cout<<setw(4)<<c[j][k];
cout<<endl;
}
cout<<"最优解为:"<<endl;
OUTPUT_SACK(c,m);
}
以上是代码 麻烦请弄成PRINTF和SCANF输出的那种！

Answer 1

#include<stdio.h>
#include<stdlib.h>
int c[50][50];
int w[10],v[10];
int x[10];
int n;
void KNAPSACK_DP(int n,int W);
void OUTPUT_SACK(int c[50][50],int k) ;
void KNAPSACK_DP(int n,int W)
{
int i,k;
for(k=0;k<=W;k++)
c[0][k]=0;
for(i=1;i<=n;i++)
{
c[i][0]=0;
for(k=1;k<=W;k++)
{
if(w[i]<=k)
{
if(v[i]+c[i-1][k-w[i]]>c[i-1][k])
c[i][k]=v[i]+c[i-1][k-w[i]];
else
c[i][k]=c[i-1][k];
}
else
c[i][k]=c[i-1][k];
}
}
}
void OUTPUT_SACK(int c[50][50],int k)
{
int i;
for(i=n;i>=2;i--)
{
if(c[i][k]==c[i-1][k])
x[i]=0;
else
{
x[i]=1;
k=k-w[i];
}
}
x[1]=(c[1][k]?1:0);
for(i=1;i<=n;i++)
printf("%4d",x[i]);
}
void main()
{
int m;
int i,j,k;
printf("输入物品个数:");
scanf("%d",&n);
printf("依次输入物品的重量:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("依次输入物品的价值:\n");
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
printf("输入背包最大容量:\n");
scanf("%d",&m);
for(i=1;i<=m;i++)
printf("%4d",i);
printf("\n");
KNAPSACK_DP(n,m);
printf("构造最优解过程如下:\n");
for(j=1;j<=5;j++)
{
for(k=1;k<=m;k++)
printf("%4d",c[j][k]);
printf("\n");
}
printf("最优解为:\n");
OUTPUT_SACK(c,m);
system("pause");
}

Answer 2

所有的Cin 改成SCANF Cout 改成printf函数

追问

不行 这样改我试过了，会直接多出一行来的。所以还需要改别的地方