动态规划法

#include 
#include 
#include 
#include 
using namespace std;
 
char x[505];
int weight[505],value[505];
int q[505][505];
int main()
{
    int i, j, length, maxWeight;
    
    scanf("%d",&length);
    scanf("%d",&maxWeight);
    for(i=1;i<=length;i++){
    	scanf("%d %d",&weight[i],&value[i]);
	}

    
	for(i = 0; i <= length; i++)
    {/// 初始化状态数组q的第一列
            q[i][0] = 0;
    }
    for(j = 0; j <= maxWeight; j++)
    {/// 初始化状态数组q的第一行
            q[0][j] = 0;
    }
    
    
    
    for(i = 1; i <= length; i++)
        {///此处 i 最后应该等于 length_x 此时为x[length_x - 1]对应于q[length_x]
            for(j = 1; j <= maxWeight; j++)
            {///此处 j 最后应该等于 length_j 此时为x[length_j - 1]对应于q[length_j]
                if(jq[i-1][j-weight[i]]+value[i]){
                	 	q[i][j] = q[i-1][j];
					}else{
						q[i][j] =q[i-1][j-weight[i]]+value[i];
					}
				
				}
            }
    	}
        for(i=0;i<=length;i++){
        	for(j=0;j<=maxWeight;j++){
        		 printf("%3d", q[i][j]);
        	}
        	 printf("n");
        }
        int r=maxWeight;
        
        for(i=length;i>=1;i--){
        	
        	if(q[i][r]==q[i-1][r]){
        		
        		x[i]=0;
        		printf("dp[%d][%d]==dp[%d][%d] ==> x[%d]=0, r=%dn",i,r,i-1,r,i,r);
			}else{
				x[i]=1;
					printf("dp[%d][%d]!=dp[%d][%d] ==> x[%d]=1, r=%dn",i,r,i-1,r,i,r-weight[i]);
				r=r-weight[i];
			}
			
		}
		int maxv=0;
		 for (int i=1;i<=length;i++){
		 	if(x[i]==1){
		 		maxv=maxv+value[i];
			 }
		 }
		 printf("maxv:%dn",maxv);
		 printf("x=[ "); 
		 for (int i=1;i<=length;i++) printf("%d ",x[i]); 
		 printf("]n");

    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
 
char x[505], y[505];
int q[505][505];
int main()
{
    int i, j, length_x, length_y;
    while(~scanf("%s %s", x, y))
    {
        length_x = strlen(x);
        length_y = strlen(y);
        for(i = 0; i <= length_x; i++)
        {/// 初始化状态数组q的第一列
            q[i][0] = 0;
        }
        for(j = 0; j <= length_y; j++)
        {/// 初始化状态数组q的第一行
            q[0][j] = 0;
        }
        for(i = 1; i <= length_x; i++)
        {///此处 i 最后应该等于 length_x 此时为x[length_x - 1]对应于q[length_x]
            for(j = 1; j <= length_y; j++)
            {///此处 j 最后应该等于 length_j 此时为x[length_j - 1]对应于q[length_j]
                if(x[i - 1] == y[j - 1])///如果两个字符相等，则等于
                    q[i][j] = q[i - 1][j - 1] + 1;///其[i - 1][j - 1]的长度 + 1
                else if(q[i][j - 1] > q[i - 1][j])///若两字符不相等且左方大于上方
                    q[i][j] = q[i][j - 1];///则该位置长度等于左方长度
                else///上方大于左方
                    q[i][j] = q[i - 1][j];
                    
          
            }///简单来讲，就算取上方和左方的最大值， max(q[i - 1][j], q[i][j - 1])
            
        }
        for(i=0;i<=length_x;i++){
        	for(j=0;j<=length_y;j++){
        		 printf("%d ", q[i][j]);
        	}
        	 printf("n");
        }
        printf("maxL:%dn", q[length_x][length_y]);///输出对应最后一个字符的长度
    }
    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
 
char x[505], y[505];
int q[505][505];
int main()
{
    int i, j, length_x, length_y;
    while(~scanf("%s %s", x, y))
    {
        length_x = strlen(x);
        length_y = strlen(y);
        for(i = 0; i <= length_x; i++)
        {/// 初始化状态数组q的第一列
            q[i][0] = i;
        }
        for(j = 0; j <= length_y; j++)
        {/// 初始化状态数组q的第一行
            q[0][j] = j;
        }
        for(i = 1; i <= length_x; i++)
        {///此处 i 最后应该等于 length_x 此时为x[length_x - 1]对应于q[length_x]
            for(j = 1; j <= length_y; j++)
            {///此处 j 最后应该等于 length_j 此时为x[length_j - 1]对应于q[length_j]
                if(x[i - 1] == y[j - 1])///如果两个字符相等，则等于
                    q[i][j] = q[i - 1][j - 1];///其[i - 1][j - 1]的长度 + 1
                else{
                	int min=q[i-1][j-1]+1;
                	if(min>q[i][j-1]+1){
                		min=q[i][j-1]+1;
					}
					if(min>q[i-1][j]+1){
						min=q[i-1][j]+1;
					}
					q[i][j]=min;
				}
                    
             
          
            }
            
        }
        for(i=0;i<=length_x;i++){
        	for(j=0;j<=length_y;j++){
        		 printf("%d ", q[i][j]);
        	}
        	 printf("n");
        }
        printf("minD:%dn", q[length_x][length_y]);///输出对应最后一个字符的长度
    }
    return 0;
}