问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。
数据：物品个数n=5,物品重量w[n]={2，2，6，5，4},物品价值V[n]={6，3，5，4，6}。
编码：
#include<iostream> using namespace std; int main(){ int i,j; int w[10],v[10]; int dp[10][100]={0}; int n,c; printf("物品个数和背包容量：\n"); scanf("%d %d",&n,&c); printf("输入物品重量和价值:\n"); for(i=1;i<=n;i++){ scanf("%d %d",&w[i],&v[i]); } for(i=1;i<=n;i++){ for(j=0;j<=c;j++){ if(j<w[i]){ dp[i][j]=dp[i-1][j]; } else dp[i][j]=dp[i-1][j]>dp[i-1][j-w[i]]+v[i]?dp[i-1][j]:dp[i-1][j-w[i]]+v[i]; } } int x[10]={0}; j=c; for(i=n;i>=1;i--){ if(dp[i][j]>dp[i-1][j]){ x[i]=1; j=j-w[i]; } } printf("%d\n",dp[n][c]); for(i=1;i<=n;i++){ printf("%d ",x[i]); } }输出结果：
可借助表格来帮助理解，重点在状态转移公式上
